### NAMES:

### LOGINS:

### PRECEPTS:

###
COS 226 Exercises on Priority Queues

*Reference: Section 2.4 in Algorithms, 4th edition (Fall 2010 Preliminary 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]`.
- Give all possible positions for the key
`N-2`
as a function of `N`.

- Repeat the same question for the key
`2`.

**2. **
Using the conventions shown in the left column of
p. 224,
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, where a letter signifies "insert a key with this value" and an asterisk signifies "remove the maximum".
(You are encouraged to use highlighters or
multiple colored pens.)