NAMES:
LOGINS:
PRECEPTS:
COS 226 Exercises on Priority Queues
Reference: Section 2.4 in Algorithms, 4th edition
1.
Suppose that an array a[] is a max-heap that contains the
distinct integer keys 1, 2, ..., N with N > 7. The key
N must
be in a[1] and the key N-1 must be in either a[2]
or a[3].
- Give all possible positions for the key N-2
as a function of N.
- Repeat the same question for the key 2.
2.
Using the conventions shown in the left column of p. 150,
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.
(Highlighters or
multiple colored pens is encouraged.)