创建最小堆或最大堆

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