爲什麼在二進制堆O（1）中插入的平均情況？

Question

如果刪除的平均情況是lg（n），這很有意義，因爲您必須執行percDown值才能保持堆的完整性，爲什麼插入和封裝堆不同？是不是相對於輸入（n）進行比較的數量除以2？

Answer 1

這是一個有趣的命題。我試圖做一個基本的計算。請確認一下，並提出計算是否有問題。它基本上是一個有一些假設的機械計算。

假設：

1. 目前已經有2^k-1元素的完全二叉樹k水平。
2. 我們增加2^k更多元素使樹具有k+1的等級。
3. 元素均勻隨機地獲得位於一個水平從[1..k]

（3）表示的是，在舊樹中的每個元件基本上由一個新的元件代替。因此向上滲透的數量將爲：

k + 2 * (k-1) + 4 * (k - 2) + ... + 2^(k-1) * 1 
= k + 2 * k + 4 * k + ... + 2^(k-1) * k - (2 + 2 * 2^2 + 3 * 2^3 + ... + (k - 1) * 2^(k-1)) 
= k * (2 + 4 + ... + 2^(k-1)) - (k * 2^k - 2 * (2^k - 1)) ......(a) 
= k * (2^k - 1) - k * 2^k + 2 ^(k+1) - 2 
= k * 2^k - k - k * 2^k + 2^(k+1) - 2 
= 2^(k+1) - (k + 2) 

（a）計算爲here。

因此，我們有2^k元素使用(2^(k+1) - (k+1) - 1)步驟過濾。因此，每個元素的平均成本是O((2^(k+1) - (k+1) - 1)/2^k) = O(2 - (k+2)/2^k)，即O(1)。

因此，我們可以假設插入成本不變。

注：如果我們假設一個元素將得到的概率0.5替代，我們可以認爲因素成以上的計算，我認爲這這將導致分工越來越接近1。

Answer 2

爲什麼它不適合插入和percUping堆一樣嗎？

當您刪除head（h）時，將它與堆中的最後一個元素交換，即最長的子樹中的最低元素（l）。將l放入更高級別的堆的概率被認爲足夠低以至於可以被忽略，因爲它已經是其子樹的最低元素。

存在特殊情況。例如，包含N個相等整數的堆將在O（1）中進行頭提取。但這不是一般情況。

Answer 3

我只是想知道當開始學習二進制堆時完全一樣的東西。我在C中編寫了一個實現，當我計算不同的操作時，這個現象讓我感到困惑。在給出一些想法之後，我的直覺是，正如其他人所提到的那樣，當移除一個元素時，它在堆中的位置被最後一個元素替代，即屬於底部的元素，因此將被保證必須沉入底部。在我的測試中，我只嘗試移除堆的頂層元素，因此這些移除總是導致遍歷整個堆的高度（log n）。

另一方面插入，將新元素放在底部，並讓它浮起來。這是我的想法，因爲堆中的大多數元素都集中在較低的層次上，所以新節點可能只有一兩個跳轉到達正確的位置。即使節點的值是整個堆的平均值，通常也不需要一直跳到堆的垂直中間層（實際上，看起來像包含2^x個元素的堆的底層，實際上包含整個堆的一半以上節點）。不知道這是否合理，但它對我有用:)。

現在，如果通過去除我們談論消除任何給定的元素，而不僅僅是最上面的一個，我不明白爲什麼平均情況應該不會有O（1）太，從那以後，我們應該是最有可能去除底部附近的東西...