SplMinHeap和decreaseKey

Question

簡短的問題：

是否有實施 SplMinHeap （或任何SPL堆），而 鬆動的表現獎金 高效 decreaseKey 法的方式進行？

背景：

對於私人的項目我玩弄實施A*類，並希望通過使用SPL堆結構之一獲得的性能提升。但我無法理解如何使用這些方法，因爲它們都缺少decreaseKey或contains方法。也許我完全錯過了一些東西？

非常感謝！

Answer 1

爲了實現decreaseKey方法，我們需要：

1. 查找堆入口和減少一個關鍵。
2. 執行上堆冒泡，直到堆順序屬性完全恢復。

除非我們需要使用最小密鑰的條目，否則根本不知道條目的存儲位置。此外，即使我們在可接受的時間內找到請求的條目，我們也無法更新其密鑰，關於SplMinHeap的方法。

所以我沒有看到用SplMinHeap數據結構實現decreaseKey方法的有效方法。例如，也許你應該實現YourHeap與YourCompleteBinaryTree通過YourArrayList實現。