gibson.. also. After reviewing your specs.. I agree, for the time being, that the resulting tree will have a root key of 1 - because this is one of the properties of a min-heap, as discussed previously. But also note, that for a queue we know that it's a FIFO structure... so we can assume what will be added to the hp min-heap when you call addToHeap, in the same respect we know that a stack employs the LIFO structure.. so we can assume what will be that popped off and added to the hp, I'm sure you know these properties... so now it's just a matter of mentally working through it.
EDIT:
Knowing the properties just mentiond, your queue becomes: 9, 5, 3, 7, 1 << which is reversed, 1 7 3 5 9 where 9 is FIFO. ie:
9
5 9
3 5 9
7 3 5 9
1 7 3 5 9
And with the stack, a slightly different happening: 2 4 6 8 where 8 is LIFO. ie:
2
2 4
2 4 6
2 4 6 8
Keep in mind that for min-heaps - the child and parent are compared and swapped if the child is less than the parent.
Now based on the code you provided above, we know that the queue is emptied/added first. Which would go something like this:
9
9
/
5 gets swapped:
5
/
9
Next is 3:
5
/\
9 3 , 3 and 5 are swapped
3
/\
9 5 , next is 7:
3
/\
9 5
/
7 , 9 and 7 are swapped:
3
/\
7 5
/
9 and last is 1 and it gets swapped/compared twice!
3
/\
7 5
/\
9 1 becomes:
3
/\
1 5
/\
9 7 and then becomes:
1
/\
3 5
/\
9 7
I believe it's more evident now how the stack will be emptied/added. I also wish there was a better way to display trees in a forum.... anyways, my resulting answer is the same as yours: B.
Just for kicks I'm going to run through it, so what's next, 8 !
1
/\
3 5
/\ /
9 7 8 looks fine here, so 6 is next:
1
/\
3 5
/\ /\
9 7 8 6 looks good here too... next is 4:
1
/\
3 5
/\ /\
9 7 8 6
/
4 , 4 gets swapped for 9:
1
/\
3 5
/\ /\
4 7 8 6
/
9 and lastly we have 2, which gets swapped compared/swapped twice:
1
/\
3 5
/\ /\
4 7 8 6
/\
9 2 becomes:
1
/\
3 5
/\ /\
2 7 8 6
/\
9 4 finally becomes:
1
/\
2 5
/\ /\
3 7 8 6
/\
9 4
Thus, B
heh.. that was fun.
