Heap Insertion

To insert a new value into the heap, we perform the following algorithm:

1. We create a node containing the new value and insert it at the next available rightmost spot in the bottom level. Thus, this value becomes the heap’s last node.

2. Next, we compare this new node with its parent node.

3. If the new node is greater than its parent node, we swap the new node with the parent node.

4. We repeat Step 3, effectively moving the new node up through the heap, until the new node has a parent whose value is greater than it.

Let’s see this algorithm in action. Here’s what would happen if we were to insert a 40 into the heap.

Step 1: We add the 40 as the heap’s last node:

Note that doing the following would have been incorrect:

Placing the 40 as a child of the 12 node makes the tree incomplete since we’d now have a node to the right of an empty position. For a heap to remain a heap, it must always be complete.

Step 2: We compare the 40 with its parent node, which happens to be the 8. Since the 40 is greater than the 8, we swap the two nodes:

Step 3: We compare the 40 with its new parent, the 25. Since the 40 is greater than the 25, we swap them:

Step 4: We compare the 40 to its parent, which is the 100. Since the 40 is smaller than the 100, we’re done!

This process of moving the new node up the heap, is called trickling the node up through the heap. Sometimes it moves up to the right, and sometimes it moves up to the left, but it always moves up until it settles into the correct position.

The efficiency of inserting into a heap is O(log N). As you saw in the previous chapter, for N nodes in any binary tree, the tree is organized into about log(N) rows. Since at most we’d have to trickle the new value up to the top row, this will take log(N) steps at most.