在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的元素必須不大於原來的值，因此整個堆的堆屬性將被保留。但是這個標準不支持，即使它在某些實現中有時會起作用。