COS 226 Exercises on Priority Queues
Reference: Section 2.4 in Algorithms, 4th edition (Fall 2010 Preliminary Edition)
Suppose that an array a is a max-heap that contains the
distinct integer keys 1, 2, ..., N with N > 7. The key
be in a and the key N-1 must be in either a
Using the conventions shown in the left column of
draw the sequence of heaps produced when the operations
P R I O * R * * I * T * Y * * Q * U E * * * U * E
are performed on an initially empty max-heap, where a letter signifies "insert a key with this value" and an asterisk signifies "remove the maximum".
(You are encouraged to use highlighters or
multiple colored pens.)
- Give all possible positions for the key N-2
as a function of N.
- Repeat the same question for the key 2.