Constructing a heap

The construct operation constructs a max heap from the given list of data items. The implementation is encapsulated in the construct function, which relies on the special properties of a complete binary tree and repeatedly applies the heapify function on the input list to convert it into a heap. Let us look at the algorithm and implementation of the construct operation on a max heap implemented as an array.

Algorithm

The algorithm for constructing a heap from a given list relies on a special property and a complete binary tree. The array representation of a complete binary tree is just its level-order traversal. Putting this the other way around, we can visualize any sequence of data items as a complete binary tree.