NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Priority Queues

References: Lecture 7 and Section 3.4 in Algs4


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. [Exercise 3.4.6] Using the conventions shown in the left column of p. 276, 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.)