在這里，將 91 添加到堆中，因此 91 將與 36 進行比較，然后與 89 進行比較，最后與 90 進行比較，因此總比較為 3 = lg8。那么當您在堆中插入一個元素時，在最大比較次數中添加 1 的原因是什么？
uj5u.com熱心網友回復：
為了驗證這一說法，確切的背景關系是至關重要的，但邊緣情況可以解釋如下：
在插入節點 91 之前，二叉堆是完美的：
__90__
/ \
89 70
/ \ / \
36 75 63 65
它有 7 個節點，因此N為 7。在這種情況下， N的以 2 為底的對數為 2。
插入 91 時，需要進行 3 次比較才能恢復堆屬性。因此，在這種特殊情況下，比較次數確實是 1 ? log 2 ?? ?。這是最壞的情況，并假設 ?? 是插入發生之前的節點數。
如果 ?? 定義為插入后的節點數，或者原始樹不是完美的，則該公式中不需要額外的 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505888.html
下一篇：求陣列中k對的絕對差的最小和