COS 226 Exercises on Priority Queues

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 15 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.

3. [Exercise 9.56] Give the binomial queue that results when the keys E A S Y Q U E S T I O N are inserted into an initially empty binomial queue. Use left-heap-ordered power-of-2 trees, as in Figures 9.19 and 9.20.