1. Consider the following values: 5, 9, 1, 5, 6, 2, 5, 6, 9, 10. Draw a binary heap for this
data.

The nodes are placed from top to bottom, left to right and then swim upwards to their
correct placement. Starting with just 5 as position 1 (top node). Then 9 gets added in
position 2. Swim 9 up to position 1 and 5 in to position 2. Then 1 gets added in position
3. Then 5 gets added in position 4, properties still hold so we can leave it. Then 6 gets
added in position 5, which needs to swim up so the 5 in position 2 becomes the 6 and
the 5 gets moved to position 5. Then the 2 gets added in position 6, and swaps with the
1 in position 3. Then the 5 gets added in position 7 and is swapped with the 2 in position
3. Then the 6 gets added on the bottom level, position 8, which needs to swim up and
swap with the 5 in position 4. Then the 9 gets added in position 9 and is swum up twice
until it is in position 2 and position 4 and 9 are now occupied by 6s. Then the 10 gets
added in position 10 and is swum up until it is in position 1, leaving the 5 that was in
position 5 now in position 10 and 9s in position 2 and position 5.
2. Is an array that is sorted in decreasing order a "max" priority queue? Explain.
An array that is sorted in decreasing order is not a “max” priority queue. Although an

array in decreasing order can be the correct “sorted” order of a priority queue, there are
additional properties that distinguish priority queues from arrays. Arrays are not aware of
their “max”, while priority queues are. The array is simply how the priority queue is
structured.
3. Why does the implementation of priority queues in the slides not use the first position in
the array? Explain.
The implementation of priority queues in the slides does not use the first position in the
array because it keeps the navigation formulas simple. The first position in the array can
be used to store the heap size.
4. Give expressions for finding the parent, left child, and right child, indices of a binary heap
node k in an implementation that does use the first index.
Parent is found as [k/2] when indexing from 1, if indexing from 0 is Math.ceil(k/2 - 1)
First child is found at 2k when indexing from 1, if indexing from 0 is 2k + 1
Second child is at 2k + 1 when indexing from 1, if indexing from 0 is 2k + 2
5. Describe a process for merging two max priority queues in O(nlogn). You may answer
for an array or linked structure implementations of a priority queue.
Create a new priority queue of the correct length
For each of the given priority queues, get the index of the max using delMax() and then if
that index is not empty, insert the next value in the input priority queue.
Looping through the elements of the queues will involve O(n) performance.
Applying delMax() on all of the elements will involve O(logn) performance.