A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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