COS 226 Exercises on Priority Queues

Reference: Section 2.4 in Algorithms, 4th edition (Fall 2010 Preliminary 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].
  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 left column of p. 224, 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.)