Building a heap in linear time (bottomup heap construction, build heap)
A heap can be built in linear time from an arbitrarily sorted array. This can be done by swapping items, ending up with an algorithm requiring at most kn+c swaps, where n is the number of items in the array and k and c are small constants.
This algorithm starts by examining the two lowest levels of the tree and organize all subtrees on those levels as binary heaps. Next, the algorithm moves one level up and heapifies those subtrees. This continues all the way to the root of the tree.
Let us consider a MinHeap
For every subtree, the priority of the root node is compared with the smaller child (the smaller of the child nodes has to be determined). If the priority of the child is less then that of the root, the items are swapped. In some cases, it is possible that the node swapped downward is still greater than the smaller child. This requires another swap in the smaller heap (subtree). This is repeated for the smaller heap as before, and the node can even be swapped all the way to the leaf. When all the levels up to the root of the whole tree have been processed, the structure is organized as a heap.
The following shows building a maximum heap
In case of a minimum heap,
line 2 would call MINHEAPIFY(A, i)
algorithm that works similarly to the MAXHEAPIFY
.
A heap with n = heapsize[A]
is built from array
A[0..n1
].
The function MaxHeapify
is called repeatedly. MaxHeapify
algorithm is called only for items A[⌊n/2⌋1],
A[⌊n/2⌋2], ..., A[0]
, because
It can be shown that the timecomplexity of the BUILDMAXHEAP algorithms is O(n).
Exercise: BuildHeap
A heap can be built from a table of random keys by using a linear time bottomup algorithm (a.k.a., BuildHeap, Fixheap, and BottomUp Heap Construction). This algorithm ensures that the heaporder property (the key at each node is lower than or equal to the keys at its children) is not violated in any node. In this exercise, the heap is visualized both as a binary tree and vector. Both visualizations illustrate the same data structure and the exercise can be completed by swapping keys in either visualization. The swapping is done by drag & dropping a key into another node. Algorithm 4 BuildMaxHeap(A)

This document was last updated 30.5.2011. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.