Problem 1
98
/ \
/ \
67 89
/ \ / \
/ \ / \
38 42 54 89
/ \
/ \
17 25
i want to insert 97 into max heap [98,67,89,38,42,54,89,17,25] (represented in list).
As per me, resulting heap is [98,97,89,38,67,54,89,17,25,42]
98
/ \
/ \
97 89
/ \ / \
/ \ / \
38 67 54 89
/ \ |
/ \ |
17 25 42
Problem 2
i want to apply delete_max() twice to the heap [100,97,93,38,67,54,93,17,25,42].
100
/ \
/ \
97 93
/ \ / \
/ \ / \
38 67 54 93
/ \ |
/ \ |
17 25 42
As per me heap after two deletemax operations,resulting heap is [93,67,93,38,42,54,25,17]
93
/ \
/ \
67 93
/ \ / \
/ \ / \
38 42 54 25
/
/
17
I want to conform, is I am doing insertion and max_delete correctly for heap and above answer is correct? If not correct, then please guide me.
Your answers look correct. Let's take a closer look at why.
In the first case, you have the heap:
[98,67,89,38,42,54,89,17,25]
You want to insert 97. So you add it to the end and then bubble it up:
[98,67,89,38,42,54,89,17,25,97]
You compare 97 with its parent (42). Since 97 is greater, you swap them:
[98,67,89,38,97,54,89,17,25,42]
Then compare 97 with its parent again. This time the parent is 67, so you have to swap again.
[98,97,89,38,67,54,89,17,25,42]
Comparing one more time, you see that the parent (98) is greater than the item you inserted, so you're done.
Now, given the heap [100,97,93,38,67,54,93,17,25,42], you want to remove the two highest items. The rule for delete_max is replace the root with the last item on the heap, and then sift it down. So you have:
[42,97,93,38,67,54,93,17,25]
42 is smaller than its children, so you swap it with the largest child:
[97,42,93,38,67,54,93,17,25]
It's greater than 38, but smaller than 67, so you swap again:
[97,67,93,38,42,54,93,17,25]
And 42 is now at the leaf level so there's nothing more to do. That's the first item removed. Now to remove the second. Move 25 to the root:
[25,67,93,38,42,54,93,17]
And sifting down:
[93,67,25,38,42,54,93,17] // swapped with 93
[93,67,93,38,42,54,25,17] // swapped with 93 again