二進制堆是否支持減鍵操作？

根據http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants，需要Θ（logn）（轉換爲O（logn））執行減鍵操作。但是，似乎沒有包含使用減少鍵操作的二進制堆實現的站點。二進制堆是否支持減鍵操作？

因此，由於Web上缺少實現，是否可以在二進制堆中執行減鍵操作？

2011-05-05 Alexandros

我認爲這是一個完全有效的問題，他要求... – Patrik 2011-05-06 22:41:57

[我在JavaScript中實現它]（https://github.com/mhluska/Snakeception/blob/master/src/binaryheap.coffee）。 – 2012-08-27 14:40:20

你可能會對[Fibonacci堆]（https://en.wikipedia.org/wiki/Fibonacci_heap）感興趣，它們有'θ（1）''reduce-key'操作 – 2016-10-30 13:49:17

我想通了這一點：

爲了執行O（LOGN）的下降鍵，我們必須知道相應的元素的提前位置。哈希映射和良好的哈希函數可以保證O（1）攤銷時間。每次修改後，我們必須更新哈希映射，這需要O（logn）。
在確定元素的位置後，我們將元素向上移動以防其元素的優先級高於其父元素（與插入方式類似），如果元素的優先級低於其子元素的優先級（在a類似的方式刪除）並更新哈希映射中的修改元素的位置。

2011-05-06 20:44:10 Alexandros

我認爲這是另一回事。散列映射的更新需要O（1），而減少鍵需要O（lg（n））。 – 2013-11-03 22:36:05

更新哈希映射爲O（log n），因爲您必須爲每個'swap（parent，child）'操作進行更新。在'reducekey'操作中有O（log n）這樣的操作。 – 2014-10-21 14:19:08

回答