A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Problem of the Last Node…Again

While the heap deletion algorithm seems straightforward, it once again raises the Problem of the Last Node.

I explained that the first step of deletion requires us to move the last node and turn it into the root node. But, how do we find the last node in the first place?

Before we solve the Problem of the Last Node, let’s first explore why insertion and deletion are so dependent on the last node anyway. Why couldn’t we insert new values elsewhere in the heap? And why, when deleting, can’t we replace the root node with some other node other than the last node?

Now, if you think about it, you’ll realize that if we were to use other nodes, the heap would become incomplete. But this begs the next question: why ...