algorithm - 创建最小堆或最大堆

Question

For creating a Min heap or a Max Heap of n elements, time taken would be O(nlogn) for creating a heap. Because, every insertion takes O(logn) time and hence n elements would take O(nlogn) time

但是在很多地方都写到堆的创建可以优化到 O(n) 时间，即线性时间？但是没有明确解释如何实现？

Answer 1

最佳方法不需要logn时间来插入节点。

The optimal method starts by arbitrarily putting the elements on a binary tree, respecting the shape property (as the tree could be represented by an array). Then starting from the lowest level and moving upwards, shift the root of each subtree downward as in the deletion algorithm until the heap property is restored. More specifically if all the subtrees starting at some height h (measured from the bottom) have already been "heapified", the trees at height h+1 can be heapified by sending their root down along the path of maximum valued children when building a max-heap, or minimum valued children when building a min-heap. This process takes O(h) swap operations per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is logn , the number of nodes at height is h. Therefore, the cost of heapifying all subtrees is:

_h=0∑^logn n/2^h+1 = O(n * _h=0∑^lognh/2^h ) which is less than

O(n * _h=0∑^∞h/2^h )

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

it is equal to O(n)

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