Checking and Removing Max

Section 30.6 Checking and Removing Max

Finding the max value in a heap is straightforward because the max value is always at the root, which is the first element in the array representation of the heap. When asked for the max value, we can simply return the element at index 0 of the array.

🔗

Insight 30.6.1.

Finding max in a heap is \(O(1)\text{.}\) It is always the first element.

🔗

Once we are done processing the max value, we will want to remove it from the heap. But this presents a problem. If we simply remove it, we will have a gap at the start of the array, which would violate the shape property of the heap. In fact, the only valid element to remove in our structure is the very last element. Removing any other element would break the shape property by creating a gap.

🔗

The array contains the values 20, 8, 12, 3, 4, 6 with an empty spot at the end.🔗 — Figure 30.6.1. The only element we can remove without causing an issue is the 6.
🔗

So, to remove the max value without breaking the heap, we first swap the root with the last element. Then we can remove the last element (which is now the max value) without creating a gap. The new root value is almost certainly not the max value, so we then need to restore the heap property.

🔗

To restore the heap property, we compare the new root with its children. If it is larger than both children, the heap property is satisfied, and we are done. If it is smaller than one or both of its children, we swap it with the larger of the two children. This ensures that the parent is larger than both children after the swap. This process is called “heapifying down”.

🔗

If we swap with a child, we then need to compare the element with its new children and continue swapping down as necessary. Eventually, we will find a spot where the current element is larger than any children it has (possibly because it ends up at a leaf).

🔗

Activity 30.6.1. Heap Removal.

The animation is ready to remove the max value. Press > to step through the process.

🔗

Then try removing more values.

🔗

Instructions.

When the > button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.

🔗

When no animation is in progress, you can use the data controls to start a new animation.

🔗

You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.

🔗

Core Controls.
- << : Skip to the beginning of the animation.
  
  🔗
- < : Step backwards one step in the animation.
  
  🔗
- > : Step forward one step in the animation.
  
  🔗
- >> : Skip to the end of the animation.
  
  🔗
- Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
  
  🔗
- Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
  
  🔗
🔗
🔗
Data Controls.
- Value Use this area to enter a value when inserting, finding, deleting, etc...
  
  🔗
🔗
🔗

🔗

The algorithm for removing the max from the heap can be summarized as follows:

🔗

function removeMax():
    swap the root with the last element
    remove the last element (which is the max)
    heapifyDown(0)

function heapifyDown(index):
    curIndex = index
    leftChildIndex = 2 * curIndex + 1
    rightChildIndex = 2 * curIndex + 2
    while leftChildIndex < size():
        // have at least one child, figure out largest
        if rightChildIndex >= size() or data[leftChildIndex] > data[rightChildIndex]:
            largerChildIndex = leftChildIndex
        else:
            largerChildIndex = rightChildIndex

        if data[curIndex] < data[largerChildIndex]:
            swap(data[curIndex], data[largerChildIndex])
            curIndex = largerChildIndex
            leftChildIndex = 2 * curIndex + 1
            rightChildIndex = 2 * curIndex + 2
        else:
            break

Most of the hard work happens in the heapifyDown function where we keep swapping the current element with its larger child until the heap property is restored. Its logic needs to handle situations where a given node has zero, one, or two children. If the left child index is out of bounds, we know there are no children, and we can stop. If only the right child index is out of bounds, we know there is only a left child. So, in determining the “largest child index”, we select the left child if the right child index is out of bounds or if the left child’s value is larger than the right child’s value. Otherwise, we select the right child.

🔗

Similar to insertion, all the work in this algorithm is constant with the exception of the loop. The loop could potentially run a number of times proportional to the height of the heap which is bounded by \(O(\log n)\text{.}\)

🔗