### NAMES:

### LOGINS:

### PRECEPTS:

###
COS 226 Exercises on Priority Queues

*Reference: Section 2.4 in Algorithms, 4th 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. 150,
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.)