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

你可以自己做:

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