原生庫中的減少鍵/增加鍵支持

Question

我注意到Java（PriorityQueue，GuavaMinMaxPriorityQueue等）和Python（heapq）中堆的大多數默認實現不支持增加鍵/減少鍵，在CLRS中描述的關鍵操作爲堆。但是，我還沒有找到解釋爲什麼是這樣的。有沒有人知道/是在文檔中描述的基本原理？

Answer 1

要修改你堆的特定元素的關鍵，你的選擇主要有：

• 已對包含該元素的堆節點的引用。這意味着你必須公開你的內部堆表示的細節，限制你的實現選項（你不能像傳統的表示那樣使用直接數組），並且通常會使你的API更難使用。
• 保持一個HashMap或類似的東西指揮每個元素到堆中的位置。這在用戶沒有修改密鑰的情況下會產生很大的開銷。

此外，爪哇Comparator小號預期是無狀態的 - 比較操作應該始終有相同的輸入一致的輸出 - 和修改鍵很少使用，很少絕對必要的，因爲需要使用最算法的優先隊列。