COS 226 Exercises on Priority Queues

NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Priority Queues

1. Suppose that an array a[] is a max-heap that contains the distinct integer keys 1, 2, ..., N with N >= 8. 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 possitions for the key N-2 as a function of N.

Repeat the same question for the key 2.

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