NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Priority Queues


1. [Exercise 9.18] The largest element in a heap must appear in position 1, and the second largest element must be in position 2 or position 3. Give the list of all positions in a heap of size 31 where the k-th largest element can appear for k = 3, 4, 5. Assume all elements are distinct.











2. [Exercise 9.22] Using the conventions of Exercise 9.1, give 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 heap.