Кучи в логарифмическом времени с использованием стандартной библиотеки C ++ - PullRequest
0 голосов
/ 03 июня 2018

У меня есть куча, используя std::make_heap:

std::vector<int> v{1,2,3,5,9,20,3};
std::make_heap(v.begin(), v.end());

Теперь я обновляю кучу, изменяя один случайный элемент:

v[3] = 35;

Есть ли способ в стандартной библиотекеОтрегулируйте кучу снова за O(log n) время, где n - это размер контейнера.В основном я ищу функцию heapify.Я знаю, какой элемент был изменен.

Я понимаю, что std::make_heap - это O(n log n) время.Я также прошел повторный вопрос, но это отличается в том смысле, что он меняет элемент max.Для этого решения уже дана O(log n) сложность в этом вопросе.

Я пытаюсь изменить любой случайный элемент в куче.

Ответы [ 4 ]

0 голосов
/ 05 августа 2018

Невозможно изменить произвольный элемент кучи во время логарифмической работы без нарушения свойства кучи, просто используя шаблоны функций std::pop_heap() и std::push_heap(), которые предоставляет стандартная библиотека.

Однако для этой цели вы можете определить свой собственный шаблон функции, подобный STL, set_heap_element():

template<typename RandomIt, typename T, typename Cmp>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value, Cmp cmp)
{
    const auto n = last - first;
    *pos = std::move(value); // replace previous value

    auto i = pos - first;
    using std::swap;

    // percolate up
    while (i > 0) { // non-root node
        auto parent_it = first + (i-1)/2;

        if (cmp(*pos, *parent_it))
            break; // parent node satisfies the heap-property 

        swap(*pos, *parent_it); // swap with parent
        pos = parent_it;
        i = pos - first;
    }

    // percolate down
    while (2*i + 1 < n) { // non-leaf node, since it has a left child
        const auto lidx = 2*i + 1, ridx = 2*i + 2;

        auto lchild_it = first + lidx; 
        auto rchild_it = ridx < n? first + ridx: last;

        auto it = pos;
        if (cmp(*it, *lchild_it))
            it = lchild_it;
        if (rchild_it != last && cmp(*it, *rchild_it))
            it = rchild_it;

        if (pos == it)
            break; // node satisfies the heap-property

        swap(*pos, *it); // swap with child
        pos = it;
        i = pos - first;
    }
}

Затем вы можете предоставить следующую упрощенную перегрузку set_heap_element() для max heap :

#include <functional> // std::less

template<typename RandomIt, typename T>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value) {
    return set_heap_element(first, last, pos, value, std::less<T>{});
}

Эта перегрузка использует объект std::less<T> в качестве объекта функции сравнения для исходного шаблона функции.


Пример

В вашем примере max-heap set_heap_element() можно использовать следующим образом:

std::vector<int> v{1,2,3,5,9,20,3};
std::make_heap(v.begin(), v.end());

// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35);

Вы можете использовать std::is_heap(), что занимает линейное время, когда вы хотите проверить* удовлетворяет ли свойство max-heap по-прежнему v после установки элемента с шаблоном функции set_heap_element() выше:

assert(std::is_heap(v.begin(), v.end())); 

Как насчет min кучи?

можно добиться того жедля min heap путем передачи объекта std::greater<int> в качестве последнего аргумента вызова функции в std::make_heap(), set_heap_element() и std::is_heap():

std::vector<int> v{1,2,3,5,9,20,3};
// create a min heap
std::make_heap(v.begin(), v.end(), std::greater<int>{});

// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35, std::greater<int>{});

// is the min-heap property satisfied?
assert(std::is_heap(v.begin(), v.end(), std::greater<int>{}));
0 голосов
/ 03 июня 2018

Если мы посмотрим поближе на ваше утверждение:

Теперь я нарушаю кучу, меняя один случайный элемент кучи.

Для кучи вO(log n) вы можете только напрямую "беспокоить" back или front вектора (что как-то соответствует вставке или удалению элемента).В этих случаях (ре) heapification может тогда быть достигнуто с помощью алгоритмов std::push_heap и std::pop_heap, которые принимают логарифмическое время работы.

Тозадняя сторона:

v.back() = 35;
std::push_heap(v.begin(), v.end()); // heapify in O(log n)

или передняя часть:

v.front() = 35;

// places the front at the back
std::pop_heap(v.begin(), v.end()); // O(log n)
// v.back() is now 35, but it does not belong to the heap anymore

// make the back belong to the heap again
std::push_heap(v.begin(), v.end()); // O(log n)

В противном случае вам необходимо переопределить весь вектор с помощью std::make_heap, что приводит к линейному запускувремя.


Сводка

Невозможно изменить произвольный элемент кучи и достичь кучи в логарифмическом времени выполнения с помощью стандартной библиотеки (т. е. шаблоны функций std::push_heapи std::pop_heap).Однако вы всегда можете самостоятельно выполнить операции кучи плавать и раковина , чтобы выполнить кучи в логарифмическом времени выполнения.

0 голосов
/ 03 июня 2018

Вы можете сделать это сами:

void modify_heap_element(std::vector<int> &heap, size_t index, int value)
{
    //while value is too large for its position, bubble up
    while(index > 0 && heap[(index-1)>>1] < value)
    {
        size_t parent = (index-1)>>1;
        heap[index]=heap[parent];
        index = parent;
    }
    //while value is too large for its position sift down
    for (;;)
    {
        size_t left=index*2+1;
        size_t right=left+1;
        if (left >= heap.size())
            break;
        size_t bigchild = (right >= heap.size() || heap[right] < heap[left] ?
                           left : right );
        if (!(value < heap[bigchild]))
           break;
        heap[index]=heap[bigchild];
        index = bigchild;
    }
    heap[index] = value;
}
0 голосов
/ 03 июня 2018

Я столкнулся с этой проблемой, связанной с желанием "обновляемой кучи".Однако, в конце концов, вместо того, чтобы кодировать настраиваемую обновляемую кучу или что-то в этом роде, я решил ее немного по-другому.

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

struct HeapElemWrapper
{
    HeapElem * e;

    size_t version;        
    double priority;

    HeapElemWrapper(HeapElem * elem)
     : e(elem), version(elem->currentVersion), priority(0.0)
    {}

    bool upToDate() const
    {
        return version == e->currentVersion;
    }

    // operator for ordering with heap / priority queue:
    // smaller error -> higher priority
    bool operator<(const HeapElemWrapper & other) const
    {
        return this->priority> other.priority;
    }
};

При извлечении самого верхнего элемента из кучи вы можете просто проверить этот элемент оболочкичтобы увидеть, если это актуально с оригиналом.Если нет, просто избавьтесь от него и вставьте следующий.Этот метод довольно эффективен, и я видел его и в других приложениях.Единственное, о чем вам нужно позаботиться, это то, что вы время от времени делаете проход по куче, чтобы очистить ее от устаревших элементов (скажем, каждые 1000 вставок или около того).

...