創建最小堆或最大堆

Question

要創建n個元素的Min堆或Max Heap，創建堆所用的時間爲O（nlogn）。因爲，每次插入需要O（logn）時間的時間，因此n個元素將需要O（nlogn）時間

但是在許多地方被寫入一個堆的創建可以被優化以O（n）的時間，即一個線性時間？但它沒有明確解釋如何？

Answer 1

最佳方法不需要登錄時間來插入節點。

的最佳方法，通過任意地穿上 二叉樹中的元素，尊重形狀屬性（作爲樹可以是由陣列表示 ）開始。然後從最低級別開始向上移動，如 刪除算法中那樣向下移動每個子樹的根，直到堆屬性被恢復。更 特別是如果開始在一些高度h（從底部測量 ）的所有子樹已經「heapified」，在高度 h+1樹木可以通過建立時下跌將自己的根沿 最大看重孩子的路徑heapified一個max-heap，或最小值 孩子時建立min-heap。此過程每個節點需要O(h)交換 操作。在這種方法中，大部分堆積需要 位於較低層。由於堆的高度爲logn, 高度處的節點數爲h。因此， heapifying所有子樹的成本爲：

_{H = 0}Σ^LOGN n/2個^{H + 1} = O（N * _{H = 0}Σ^LOGN H/2 ^ħ），這是小於

爲O（n * _{H = 0}^Σ∞ H/2 ^ħ）

since h/2h converges to 2 as it is an infinite series 

它等於O(n)

來源：http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap