Looking for the Last Node

While the insertion algorithm seems straightforward, there’s one little snag. The first step has us place the new value as the heap’s last node. But this begs the question: how do we find the spot that will be the last node?

Let’s take a look again at the heap before we inserted the 40:

We know by looking at the diagram that to make the 40 into the last node, we’d make it the right child of the 8, as that’s the next available spot in the bottom row.

But a computer doesn’t have eyeballs and doesn’t see the heap as a bunch of rows. All it sees is the root node, and it can follow links to child nodes. So how do we create an algorithm for the computer to find the spot for the new value?

Take our example heap. When we start at the root node of 100, do we tell the computer to look among the 100’s right descendants to find the next available spot for the new last node?

While it’s true that in our example heap the next available spot is among the 100’s right descendants, take a look at the following alternative heap:

In this heap, the next available spot for the new last node would be the 88’s right child, which is among the 100’s left descendants.

Essentially, then, just as it’s impossible to search through a heap, it’s impossible to efficiently find the heap’s last node (or next available spot to hold a new last node) without having to inspect each and every node.

So how do we find the next available node? I’ll explain this later on, but for now, let’s call this issue the problem of the last node. I promise we’ll come back to it.

In the meantime, let’s explore the heap’s other primary operation, which is deletion.