The IndexMaxPQ class represents an indexed priority queue of generic keys. It supports the usual Insert and Delete-the-maximum operations, along with Delete and Change-the-key methods. In order to let the client refer to items on the priority queue, an integer between 0 and maxN-1 is associated with each key. The client uses this integer to specify which key to delete or change. It also supports methods for peeking at a maximum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap along with an array to associate keys with integers in the given range. The Insert, Delete-the-maximum, Delete, Change-key, Decrease-key, and Increase-key operations take logarithmic time. The IsEmpty, Count, Max-index, Max-key, and Key-of operations take constant time. Construction takes time proportional to the specified capacity.