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.