You have to check both of the child nodes. The rules for removing from a binary max heap are:
- The result is the node at the top of the heap (i.e. the root).
- Move the item from the end of the heap to the top of the heap.
- 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.