Question $1$: Standby Passenger List $($Heaps and Priority Queues$)$

The airline has just given you the list of standby passengers. They have assigned their preferences

$($bigger is better$)$ to each customer but have not ordered the passenger list. There is still $30$mins

before departure and might need to add new passengers to the list or change the preference for a

passenger already on the list. You place the current unordered passenger list into a good old fashion

array.

Passenger $($Index$)01234567$

Preference $($Value$)$

You could just sort this array, but if another standby passenger comes along you have to sort all over

again and you are only interested in the passenger with highest preference at any one time. You

decided to use a Priority Queue with a Heap!

$($a$)$ Draw the complete binary tree that corresponds to the given ordering of passengers. Why does

the tree not constitute a heap yet?

$($b$)$ It is time to figure out which passenger has the highest preference. Using the initial list given

above and the Batch Insert algorithm is used to sort the elements into a partial ordering, so as to

produce a heap. Fill in the values of the array after it has been partially sorted using the Batch Insert

algorithm. Hint: A useful way to solve this problem is to draw the initial tree and all subsequent

trees that are produced by the Batch Insert algorithm, and then to fill in the elements of the array

using your diagram of the final tree in the sequence.

Index $01234567$

Value

$($c$)$ Another passenger arrives with a preference value of $100.$ Fill in the elements of the array after

adding the passenger to the queue.

Index $01234567$

Value

$($d$)$ Time to board and there are $2$ seats currently available. What does the array look like after two

items are dequeued$/$polled from the queue?

Index $01234567$