CODEWITHSUNDEEP
java
Sean
Sean

Reputation: 789

interpreting this for loop snippet

Here we have a snippet of an array implementation of a binary heap. I would like some help seeing what this for loop means in pseudocode:

public void insert (Anytype x) { 
    int hole = ++currentSize; //currentSize is the size of the array
    for (array[0] = x; x.compareTO(array[hole / 2]) < 0; hole /= 2)
        array[hole] = array[hole / 2];
    array[hole] = x;
}

I can't seem to understand how this for loop works. Thank you.

EDIT filled the hole

Upvotes: 0

Views: 130

Answers (2)

Aki Suihkonen
Aki Suihkonen

Reputation: 20027

An array converted into a binary heap can be seen as follows

         [elem 0] <-- put the inserted element here? (why? a precaution perhaps?)

         [element 1]...
    [element2] [ element3 ]  
[elem4][elem5] [elem6][elem7]  
[x][x] [x][x]  [x][XX] ... <-- unoccupied

The code travels to the parent of each node by dividing the index hole by 2. Then it moves the parent up to the current node, if parent > current node.

There's a mistake I think... At least this is not the typical solution, where one puts the inserted element as the last non occupied 'hole' and travels up from that position....

The correct method is just start comparing the parent of the last element and iterate towards root. There is no need to swap, but where ever index 'hole' ends, that's the proper place to finally put the new element. (The typical solution puts 'X' in the last position and swaps, but that is inefficient. ) Also the first initialization in the for loop is unnecessary.

Anyway, the index arithmetic works when index 0 is omitted.

Upvotes: 1

Choclatey Shatner
Choclatey Shatner

Reputation: 241

I'm not quite sure what you're looking for, but here goes:

compareTo returns an int. x.compareTo(y) returns a negative number if x is less than y.

So the code roughly does this:

for( set the first pos in the array to x; if x is less than array[hole/2]; hole/=2){
   array[hole] = array[hole/2];

Set your arr[final val of hole] to x

Upvotes: 0

Related Questions