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].
  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. 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.)