在O(logn)时间内使用STL堆实现Decrease Key

Question

目前STL Heap不支持reduce键,但是可以直接更改向量上的值并再次调用make_heap,即O(n)时间.但是,这不如二进制堆减少密钥有效,这将占用O(logn)时间.

有没有办法使用STL堆函数实现O(logn)时间？

Answer 1

我很确定没有符合标准的方法来做到这一点 -维基百科也这么说：

没有对减少/增加键操作的标准支持

尽管它确实指向了图书馆gheap，但它很值得一看。

这里的问题是，标准没有规定堆结构采用什么形式，也没有规定操作的执行方式。（总的来说，这是一件好事。）

如果实现使用标准二进制堆，那么我认为您可以简单地减少 at 的元素heap[i]，然后调用push_heap(heap.begin(), heap.begin() + i + 1)，这将执行必要的向上堆操作。最终位于该位置的元素i必须不大于原来的值，因此整个堆的堆属性被保留。但是，即使有时在某些实现中确实有效，标准也不支持这一点。

Answer 2

您可以使用pop_heap后跟递减值，后跟push_heap：

int main() {
    //Create the heap
    std::vector<int> heap{1,2,3,4,5,6,7};
    std::make_heap(heap.begin(), heap.end());

    //Decrease key
    std::pop_heap(heap.begin(), heap.end());
    --*(std::prev(heap.end()));
    std::push_heap(heap.begin(), heap.end());
}

编辑：这是您的意思，还是您希望能够减少堆中任何元素的键？