NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Priority Queues

Reference: Section 2.4 in Algorithms 4/e


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].
  1. Give all possible positions for the key N-2 as a function of N.











  2. Repeat the same question for the key 2.









2. Using the conventions shown in the right column of p. 319, 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.)