使用 C++ 标准库以对数时间进行 Heapify

Question

我有一个堆使用 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)时间。我也经历过重复的问题，但在改变最大元素的意义上是不同的。因为该解决方案已经在该问题中给出了 O(log n) 的复杂性。

我正在尝试更改堆中的任何随机元素。

Answer 1

我也一直面临着想要 "updateable heap" 的问题。然而，最后，我没有编写自定义可更新堆或类似的东西，而是以不同的方式解决了它。

要保持对最佳元素的访问而无需显式遍历堆，您可以对要排序的元素使用版本化包装器。每个唯一的、真实的元素都有一个版本计数器，每次元素更改时都会增加。然后堆内的每个包装器都带有元素的一个版本，即创建包装器时的版本：

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 次左右的插入）遍历堆以清除过时的元素。

Answer 2

如果我们仔细查看您的陈述：

now I disturb heap by changing one random element of heap.

在O(log n)堆化只能直接"disturb"向量的back或front （以某种方式对应于插入或删除元素）。在这些情况下，（重新）堆化可以通过 std::push_heap and 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）无法修改堆的任意元素并以对数运行时间实现堆化.但是，您始终可以自己实现堆的 swim 和 sink 操作，以便在对数运行时间内堆化。

Answer 3

你可以自己做:

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;
}

Answer 4

只需使用函数模板 std::pop_heap() 和 [=16] 即可在不违反堆属性的情况下以对数运行时间修改堆的任意元素=] 标准库提供。

但是，您可以为此目的定义自己的类似 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;
    }
}

然后，您可以为 max 堆 提供以下 set_heap_element() 的简化重载：

#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 堆怎么样？

您可以通过将 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>{}));

使用 C++ 标准库以对数时间进行 Heapify

Heapify in logarithmic time using the C++ standard library

c++

algorithm

heap

stl

data-structures

总结

例子

min 堆怎么样？