Binary heap insertion, don't understand for lo

Question

In Weiss 'Data Structures and Algorithms In Java", he explains the insert algorithm for binary heaps thusly

public void insert( AnyType x )
{
    if( currentSize == array.length -1)
        enlargeArray( array.length * 2 + 1);

    // Percolate up
int hole = ++currentSize;
for(array[0] = x; x.compareTo( array[ hole / 2 ]) < 0; hole /=2 )
    array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}

I get the principle of moving a hole up the tree, but I don't understand how he's accomplishing it with this syntax in the for loop... What does the initializer array[0] = x; mean? It seems he's overwriting the root value? It seems like a very contrived piece of code. What's he doing ere?

Answer 1

First off, I got a response from Mark Weiss and his email basically said the code was correct (full response at the bottom of this answer).

He also said this:

Consequently, the minimum item is in array index 1 as shown in findMin. To do an insertion, you follow the path from the bottom to the root.

Index 1? Hmmm... I then had to go back and re-read larger portions of the chapter and when I saw figure 6.3 it clicked.

The array is 0-based, but the elements that are considered part of the heap is stored from index 1 and onwards. Illustration 6.3 looks like this:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   | A | B | C | D | E | F | G | H | I | J |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13

The placing of the value at element 0 is a sentinel value to make the loop terminate.

Thus, with the above tree, let's see how the insert function works. H below marks the hole.

First we place x into the 0th element (outside the heap), and places the hole at the next available element in the array.

                                              H
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| x | A | B | C | D | E | F | G | H | I | J |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13

Then we bubble up (percolate) the hole, moving the values up from "half the index" until we find the right spot to place the x.

If we look at figure 6.5 and 6.6, let's place the actual values into the array:

                           H/2                           H
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 |    |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13

Notice that we placed 14, the value to insert, into index 0, but this is outside the heap, our sentinel value to ensure the loop terminates.

Then we compare the value x with the value at hole / 2, which now is 11/2 = 5. x is less than 31, so we move the value up and move the hole:

            H/2             H <---------------------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
                            |                             ^
                            +--------- move 31 -----------+

We compare again, 14 is again less than 21 (5 / 2 = 2), so once more:

       H/2   H <------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
             |              ^
             +-- move 21 ---+

Now, however, 14 is not less than 13 (hole / 2 --> 2 / 1 = 1), so we've found the right spot for x:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 14 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
             ^
             x

As you can see, if you look at illustrations 6.6 and 6.7, this matches the expected behavior.

---

So while the code isn't wrong, you got one little snag that is perhaps outside of scope of the book.

If the type of x being inserted is a reference type, you will in the current heap have 2 references to the same object just inserted. If you then immediately delete the object from the heap, it looks (but look where looking like got us in the first place...) like the 0th element will still retain the reference, prohibiting the garbage collector from doing its job.

---

To make sure there's no hidden agenda here, here is the complete answer from Mark:

Hi Lasse,

The code is correct.

The binary heap is a complete binary tree in which on any path from a bottom to the root, values never increase. Consequently the minimum item is at the root. The array representation places the root at index 1, and for any node at index i, the parent is at i/2 (rounded down) (the left child is at 2i and the right child at 2i+1, but that is not needed here).

Consequently, the minimum item is in array index 1 as shown in findMin. To do an insertion, you follow the path from the bottom to the root.

In the for loop:

hole /= 2 expresses the idea of moving the hole to the parent.

x.compareTo( array[ hole / 2 ]) < 0 expresses the idea that we stay in the loop as long as x is smaller than the parent.

The problem is that if x is a new minimum, you never get out of the loop safely (technically you crash trying to compare x and array[0]). You could put in an extra test to handle the corner case. Alternatively, the code gets around that by putting x in array[0] at the start, and since the "parent" of node i is i/2, the "parent" of the root which is in index 1 can be found in index 0. This guarantees the loop terminates if x is the new minimum (and then places x, which is the new minimum in the root at index 1).

A longer explanation is in the book... but the basic concept here is that of using a sentinel (or dummy) value to avoid extra code for boundary cases.

Regards,

Mark Weiss

Answer 2

The array initialiser looks wrong. If it were array[hole] = x;, then the whole thing makes perfect sense.

It first puts the value in the lowest rank of the tree (the entry after the current size), then it looks in the entry `above it' by looking at (int) hole/2.

It keeps moving it up until the comparator tells it to stop. I think that this is a slight misuse of the syntax of a for loop, since it feels like its really a while(x.compare(hole/2) < 0) type loop.