在O（logn）时间使用STL堆执行减少键

Question

目前STL堆不支持减少键，但是可以直接更改矢量上的值并再次调用make_heap，即O（n）时间。然而，这并不像二进制堆减少密钥那样有效，这会花费O（logn）时间。

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

Answer 1

可以使用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()); 
} 

编辑：这是你的意思，还是你希望能够降低任何元素的关键在堆？

Answer 2

我敢肯定有做的不符合标准的方式 - Wikipedia says so too：

没有为减少/增加键操作

虽然它去没有标准支持指向gheap库，这可能值得一看。

这里的问题是标准没有规定堆结构需要什么形式，也没有规定如何执行操作。 （通常这是件好事。）

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