分鐘堆比O（logn）增加鍵好？

Question

我使用的是一個優先級隊列，它最初基於啓發式元素的優先級。當元素出隊時，啓發式被更新，當前隊列中的元素可能會增加鍵值。

我知道有堆（特別是斐波那契堆）已經攤銷O（1）減少關鍵操作，但是有沒有堆結構在增加關鍵操作時有相似的邊界？

對於我的應用程序來說，這遠不是性能問題（一個二進制堆能夠正常工作），它實際上只是關於學術好奇心。

編輯：爲了澄清，我正在尋找一個數據結構，它的運行速度比O（logn）時間快，而不是減少鍵。由於啓發式估計優先級，我的應用程序永遠不會減少密鑰。

Answer 1

二進制堆太不靈活，無法擊敗對數複雜度。 二項式堆只允許更有效的連接操作。

具有良好的降低，主要性能其他堆是pairing heaps和2-3 heaps

Answer 2

二項堆取O（log n）的時間減少按鍵操作！這不是比斐波那契堆慢嗎？

Answer 3

其實，在斐波那契堆中，增加鍵操作與減少鍵相同。恕我直言，這只是一個傳統的命名操作「減少鍵」，因爲它在一些算法中使用。但斐波那契堆實現允許兩者。