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 of 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.

Now the problem boils down to converting the complete binary tree to a heap. Since it is a complete binary tree, it already follows one of the requirements to be called a heap. The other requirement is that the value at any node should be greater than its children. To enforce this second requirement, we can traverse from the last node to the root node and, at each iteration, run a down-heapify operation to make sure the current node is greater than both its children.