Algorithm to delete root node from binary max heap

Question

I'm sitting here looking at an algorithm for deleting the root node in a binary max heap, and then update the tree with a new root. Here's how it looks:

if (n==0) {
  empty = true;
} else {
  empty = false;
  top = a[1];
  a[1] = a[n];
  n = n-1;
  parent = 1;
  child = 2;

  while (child<=n-1) {
    if (tab[child]<tab[child+1]){
      child = child+1;
    }
    if (tab[child]>tab[parent]) {
      swap[tab[child],tab[parent]);
      parent=child;
      child=parent*2;
    } else {
      child=n;
    }
  }
}

So, what I don't understand is why it says:

while(child<=n-1)

I mean, lets say we have a heap with 11 nodes, including the root node. When we delete the root node, we're left with 10 nodes. According to this code, the loop should stop if child = 10. But how does that make sense? Even if child = 10 and parent = 5, shouldnt it still run the if's to see if child > parent? Why would it not check that scenario, but stop the loop instead?

Hope this makes sense. Sorry if it's obvious, i've been looking at heaps and nodes the whole day and my head is no longer cooperating.

Answer 1

You have to check both of the child nodes. The rules for removing from a binary max heap are:

1. The result is the node at the top of the heap (i.e. the root).
2. Move the item from the end of the heap to the top of the heap.
3. While the item you inserted is smaller than the largest of its children, swap it with the largest child.

Your code is not doing step 3 correctly. You first have to determine which is the largest child.

I suspect the code is using (child <= n-1) because it assumes that you will be checking the items at child and child+1 in order to satisfy the requirements of step 3.

Added after post was modified

I think that (child <= n-1) is a bug. It should be:

while (child <= n)
{
    if (child < n && tab[child] < tab[child+1])
    {
        child = child+1;
    }

Otherwise, as you say, there is the potential of failing to make a comparison.

Answer 2

Don't forget that child is only the index of your array in which you stored the binary heap. Meaning that if you arrived at the nth element you can stop because the last element was removed from the tree.

You never compare child with parent but rather tab[child] with tab[parent]!