HeapWS

Draw arrows from each element to its children: (index * 2 + 1 or + 2)

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16

Insert the following values into a min heap one at a time. Show the array after each insertion

50, 45, 40, 35, 30, 25, 20, 15, 10, 5

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
50
30 / 35 / 45 / 50 / 40 / Should look like this at this point…
5 / 10 / 25 / 20 / 15 / 45 / 30 / 50 / 35 / 40

Draw the final array as a tree:

Remove the top value three times. Show the array after each removal.

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
5 / 10 / 25 / 20 / 15 / 45 / 30 / 50 / 35 / 40
25 / 35 / 30 / 50 / 40 / 45 / One more remove top should produce this

Over…

Open the MinHeap project

1) Complete the add function. The existing code adds the value to the end of the array and finds the index of its parent. You need add a loop to swap the value up until it finds its correct location.

while(we are not at root)

get index of parent
if smaller than parent

swap current and parent

update current index to where parent was

else break

To get the parent:

int parentIndex = getParentIndex(curIndex);

The final array should look like the one from the front side of the sheet.

2) Complete the removeTop function. The existing code swaps the first and last elements, decrements the size. Then, starting from the new root (index 0) we need to swap down until the value finds its resting place.The existing loop continues until we reach the second half of the array. At that point we are in a "leaf" element and know that there are no more children to swap with.

Missing is the logic to find the smaller child of the current element. Once identified, if it is smaller than the current element, we need to swap with that child and then repeat the check with our new children. If the smallest child is larger than the current value, we can stop the process.

To get the leftChild index (same idea for right child):

int leftIndex = getLeftChildIndex(curIndex);