Again, An Easy Process

Popping Off The Top

Having looked at how to add a value to a heap, the next obvious step is to see how to take one out. Like the addition operation, the removal operation is pretty simple and straightforward although it is slightly more complicated than adding for reasons you will recognize soon. Here is the process.

Acquire the value from the first element at index zero

1. Assign the value of the last value at size minus one to the first element at index zero


2. Starting at the first element, resolve the heap by moving smaller values up, a process called trickling down

The trickle down process is provided here.

   // find the children's indices from the current one

   // check for both child indices less than the array size

      // check for either of the children to be smaller than the parent

         // swap the parent with the smallest of the two children

         // call the function recursively with that child's index

   // check for only the left child index less than the array size

      // check for the left child to be smaller than the parent

         // swap the left child's value with the parent's value

         // call the function recursively with the left child's index

To be clear, the above algorithm may not be the most efficient; there are a variety of ways to conduct this operation. However, the important thing to note is that the condition with two children is handled, AND the condition with one child -- which will be the left child thanks to the tree being complete -- is handled. As long as both circumstances are considered, the trickle down operation will be successful.

Like the data addition to a heap, the data removal process is also dynamic so it is better to view this in the video. You will be able to follow the whole process this way.

This wraps up the heap operations. This is an impressive use of someone who could imagine a picture of one data structure overlaid on top of another. This is both the real science and art of Computing Science.

Onward.