爲什麼會在自我平衡二叉搜索樹上使用堆？

Question

堆有什麼用途？無論堆可以做什麼也可以通過像AVL樹一樣的自平衡二叉搜索樹來完成。堆最常見的用法是找到最小（或最大）元素（時間始終是根）。通過保持指向最小（或最大）元素的指針來構造AVL樹時，也可以包含此功能，並且最小/最大查詢可以在時間內回答。

我能想到的AVL樹的唯一好處是AVL樹因爲指針而使用更多的內存。在AVL樹上使用堆還有其他優勢/功能嗎？

Answer 1

堆可能有更好的插入和合並時間。這實際上取決於堆的類型，但通常它們比AVL嚴格得多，因爲它們不必擔心每次操作後的自動平衡。

一堆只能保證所有節點遵循堆中相同的排序方式。當然，像二叉堆這樣的更嚴格的堆使得插入和合並更加困難，因爲排序更重要，但情況並非總是如此。

例如，Fibonacci堆的插入和合並時間將爲O(1)與AVL的O(log n)。

與堆相比，構建完整的AVL也更困難。

當我們只想快速訪問最小和最大項目並且不關心其他元素的完美排序時，我們通常會使用堆棧。通過快速插入，我們可以快速處理很多元素，並始終關注最重要的（或最不重要的）元素。

Answer 2

當你說一個自平衡二叉樹可以做比堆更嚴格的事情，並且堆使用更少的指針空間時，你是正確的。以下是一些其他注意事項：

• 與AVL樹相比，二進制堆實現的代碼要少得多。這使得編碼，調試和修改更加容易。

• AVL樹使用一個對象容器和每個數據項存儲兩個指針。二進制堆使用每個數據項存儲零開銷 - 它全部打包到一個數組中。

Answer 3

的主要原因是二元堆實際上爲陣列，而不是樹（樹是一個隱喻，實際執行是一個數組，其中元素的索引爲i孩子是具有索引元件來實現2i+1和2i+2）。由於locality of reference，數組在空間和時間上都比樹更高效（常量中），這使得數據結構的緩存效率更高，這通常會導致更好的常量。

另外，initializing a binary heap與n元素需要O(n)時間，而對BST做同樣的操作需要O(nlogn)時間。