algorithm - Creating a Min heap or a Max heap

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

But in many places it is written that the creation of a heap can be optimized to O(n) time i.e. a linear time?But it is not clearly explained how?

Answer 1

The optimal method doesn't need logn time for inserting a node.

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∑<sup>logn n/2^h+1 = O(n * _h=0∑<sup>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)

Source: http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap