Inserting an item in the heap

The insert operation is a primary operation on a heap used to insert a value. The implementation is encapsulated in the insert function, which inserts a new node in the binary tree and ensures the resulting tree still follows the max-heap property. Let us look at the algorithm and implementation of the insert operation on a max heap implemented as an array.

Algorithm

The algorithm for inserting a new value in a heap is quite simple. Since the heap is a complete binary tree, we insert a new node at the first available free spot. When implemented in an array, this free spot is the index after the last element of the heap in the array.

The newly inserted node might violate the heap property in the resulting tree, so we recalibrate the tree to enforce the heap property. To do this, we traverse upwards from the newly inserted node and compare the current node with its parent at each iteration. If the value at the child node is larger than the parent, we swap the nodes. The traversal stops when we reach the root node, or the current node is no longer larger than its parent.