Вопрос по heap, c++, median – C ++ реализует функцию медианы кучи

4

После ответа, найденного здесь,https://stackoverflow.com/a/10931091/1311773Я пытаюсь реализовать две кучи, чтобы я мог рассчитать текущую медиану.

Я не знаком с кучами и не уверен, с чего начать реализацию этой функции, описанной здесь.http://programmingpraxis.com/2012/05/29/streaming-median/

Моя цель состоит в том, чтобы создать небольшую тестовую программу, которая бы эффективно рассчитывала текущие медианы, так что по мере роста списка медиана не нуждается в пересчете с нуля. Используя две кучи, я должен быть в состоянии сделать это, я просто шокирован тем, как начать это реализовывать.

Любые советы по этому вопросу будут оценены.

использовать std :: priority_queue jxh
Куча - это тип дерева или векторный массив? Edge

Ваш Ответ

2   ответа
4

std::priority_queue Шаблон предоставляет все свойства кучи. Максимальное или минимальное извлечение постоянного времени (в зависимости от того, как сравниваются элементы) и логарифмическое время вставки. Это можно найти в<queue> заголовочный файл

По умолчаниюpriority_queue это макс-куча.

int numbers[11] = { 0, 9, 3, 4, 8, 12, 2, 11, 10, 1, 5 };
std::priority_queue<int> myheap(numbers, numbers + 11);
std::cout << "biggest " << myheap.top() << std::endl; // 12
myheap.pop();
std::cout << "biggest " << myheap.top() << std::endl; // 11
myheap.push(6);
std::cout << "biggest " << myheap.top() << std::endl; // 11
myheap.push(13);
std::cout << "biggest " << myheap.top() << std::endl; // 13

Вот пример того, как создать минимальную кучу:

std::priority_queue<
    int,
    std::priority_queue<int>::container_type,
    std::greater<int>
>;

Для реализации алгоритма медианного потока подход подобен следующему:

create a max-heap for items that are smaller than the median create a min-heap for items that are greater than the median when pushing new items into the heap decide which heap it should be pushed into, and push it there if one of the heaps' size is more than 1 greater than the other heap, then pop the bigger one, and put that element into the smaller one

Тогда медиана - это либо вершина большей кучи, либо среднее значение вершин обеих куч.

Если вы чувствуете, что вам нужно управлять кучей вручную,C++ предоставляет алгоритмы, которые позволяют вам делать это на вашей собственной структуре данных произвольного доступа.

std::make_heap -- heapify a region specified by iterator endpoints std::push_heap -- assumes the first N-1 elements are already a heap, and incoporates the N'th element into the heap std::pop_heap -- places the first element in the region into the last position, and reheapifies the region, but leaving the last element alone
Каковы скорости и стоимость этого алгоритма, а также объем памяти? Является ли использование метода кучи для вычисления медианы бега быстрее, чем просто использование чего-то вроде Quickselect снова и снова? Edge
@Andrew: В Википедии есть хорошая статья об алгоритме кучи.
Я не могу найти какие-либо ресурсы в коде для его реализации. Я не очень хорошо разбираюсь в шаблонах или о том, куда идти с приоритетом приоритета. Я понимаю, что он поставляется с множеством встроенных функций. Edge
@ Андрей: я привел несколько примеров, надеюсь, это поможет.
0

    #include<cstdio>
    #include<iostream>
    #include<queue>
    #include <vector>         
    #include <functional>

    typedef priority_queue<unsigned int> type_H_low;
    typedef priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > type_H_high;

    size_t signum(int left, int right) {
        if (left == right){
            return 0;
        }
        return (left < right)?-1:1;
    }

    void get_median( unsigned int x_i, unsigned int &m, type_H_low *l, type_H_high *r) {

        switch (signum( l->size(), r->size() )) {
        case 1: // There are more elements in left (max) heap
            if (x_i < m) {
                r->push(l->top());
                l->pop();
                l->push(x_i);
            } else {
                r->push(x_i);
            }
            break;

        case 0: // The left and right heaps contain same number of elements
            if (x_i < m){
                l->push(x_i);
            } else {
                r->push(x_i);
            }
            break;

        case -1: // There are more elements in right (min) heap
            if (x_i < m){
                l->push(x_i);
            } else {
                l->push(r->top());
                r->pop();
                r->push(x_i);
            }
            break;
        }

        if (l->size() == r->size()){
            m = l->top();
        } else if (l->size() > r->size()){
            m = l->top();
        } else {
            m = r->top();
        }

        return;
    }

    void print_median(vector<unsigned int> v) {
        unsigned int median = 0;
        long int sum = 0;
        type_H_low  H_low;
        type_H_high H_high;

        for (vector<unsigned int>::iterator x_i = v.begin(); x_i != v.end(); x_i++) {
            get_median(*x_i, median, &H_low, &H_high);
            std::cout << median << std::endl;
        }
    }
Вы уже опубликовали этоexact same answer на другой вопрос. Я рекомендую оставить только один из них (возможно, другой, так как это гораздо более популярный вопрос), но если вы решите оставить этот вопрос, пожалуйста,edit это исправить отступ и добавить некоторые комментарии, как я там написал. Спасибо!

Похожие вопросы