這是我不太明白的事情。當我閱讀有關堆的文獻時，總是說堆的最大優勢是您可以立即使用頂部（如果是最大堆，則為最大）元素。但是您不能只使用 BST 并存盤指向同一節點（最右下角）的指標并使用插入/洗掉來更新指標嗎？
如果我沒記錯的話，使用我所描述的 BST 實作，您將擁有
================================================
| Insert | Remove Max
================================================
Special BST | O(log(n)) | O(1)
================================================
Max Heap | O(log(n)) | O(log(n))
================================================
讓它變得更好。
偽代碼：
Insert:
Same as regular BST insert, but can keep track of whether
item inserted is max because traversal will be entirely
in the right direction.
Delete
Set parent of max equal to null. Done.
我在這里想念什么？
uj5u.com熱心網友回復：
但是您不能只使用 BST 并存盤指向同一節點（最右下角）的指標并使用插入/洗掉來更新指標嗎？
是的，你可以。
使用我正在描述的 BST 實作，您將 [...] Remove Max O(1) [...] 使其變得更好。[...] 將 max 的父級設定為 null。完畢。
不，最大移除不會（總是）是 O(1)，原因如下：
洗掉 Max 后，您還需要更新指標以參考最右下角的節點。例如，在移除 Max 之前，以這棵樹為例：
8 / \ 5 20 <-- Max pointer / / 2 12 / \ 10 13 \ 14您必須找到值為 14 的節點，以便更新 Max 指標。
通過保持樹的平衡，可以使上述操作為 O(1)，比方說根據 AVL 規則。在這種情況下，前一個 Max 節點的左子節點將沒有右子節點，而新的 Max 節點將是它的左子節點，或者如果它沒有左子節點，則是它的父節點。但是由于某些洗掉會使樹不平衡，因此需要在它們之后進行重新平衡操作。這可能涉及幾次輪換。例如，以這個平衡的 BST 為例：
8 / \ 5 13 / \ / \ 2 6 9 15 <-- Max pointer / \ \ \ 1 4 7 10 / 3去掉節點 15 后，很容易確定 13 是下一個 Max，但是以 13 為根的子樹將不平衡。平衡它之后，整個樹是不平衡的，需要再次旋轉。旋轉次數可以是 O(logn)。
最后，您可以使用帶有 Max 指標的平衡 BST，但提取 Max 節點仍然是 O(logn) 操作，其時間復雜度與二叉堆中的相同操作相同。
二叉堆能做什么而二叉搜索樹不能？
考慮到二叉堆不使用指標，因此“管理”開銷比自平衡 BST 少得多，插入/洗掉操作的實際空間消耗和運行時間會更好——而它們的漸近復雜度是相同。
此外，可以在 O(n) 時間內從未排序的陣列構建二進制堆，而構建 BST 的成本為 O(nlogn)。
但是，當您需要能夠以正確的順序遍歷值、查找值或查找值的前任/繼任者時，BST 是一種可行的方法。對于此類操作，二叉堆的時間復雜度更差。
uj5u.com熱心網友回復：
最大堆和平衡 BST（例如 AVL 樹）都在 O(log n) 時間內執行這些操作。但是由于指標，BST 占用了更多空間，并且它們的代碼更復雜。
uj5u.com熱心網友回復：
由于您談論的是 BST 而不是平衡 BST，因此請考慮以下傾斜的 BST：
1
\
2
\
3
\
...
\
n
您可以保存對 max ( n-th) 元素的指標參考，但如果您要插入一個 value ，在最壞的情況下< n將需要插入時間。O(n)此外，要查看堆中的最大值，您可以簡單地heap[0]（假設堆是使用陣列實作的）來及時O(1)獲取堆中的最大元素。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/475519.html
下一篇：這個演算法的時間復雜度是多少？