使用 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

如果我们仔细看看你的陈述：

现在我通过改变堆的一个随机元素来干扰堆。

对于堆化，O(log n)您只能直接“干扰”向量的后面或前面（这以某种方式对应于插入或删除元素）。在这些情况下，可以通过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），不可能修改堆的任意元素并在对数运行时实现堆化。但是，您始终可以自己实现堆的游泳和下沉操作，以便在对数运行时间内进行堆化。

Answer 2

你可以自己做：

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