Package algs24

Class IndexMaxPQ<K extends Comparable<? super K>>

java.lang.Object
algs24.IndexMaxPQ<K>
All Implemented Interfaces:
Iterable<Integer>
public class IndexMaxPQ<K extends Comparable<? super K>> extends Object implements Iterable<Integer>
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 NMAX-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 the maximum key, testing if the priority queue is empty, and iterating through the keys.

The insert, delete-the-maximum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, max-index, max-key, and key-of operations take constant time. Construction takes time proportional to the specified capacity.

This implementation uses a binary heap along with an array to associate keys with integers in the given range.

For additional documentation, see Section 2.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private class 
    IndexMaxPQ.HeapIterator
     

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private K[]
    keys
     
    private int
    N
     
    private int[]
    pq
     
    private int[]
    qp
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    IndexMaxPQ(int NMAX)
    Create an empty indexed priority queue with indices between 0 and NMAX-1.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    change(int i, K key)
    Deprecated.
    Replaced by changeKey()
    void
    changeKey(int i, K key)
    Change the key associated with index i to the specified value.
    boolean
    contains(int i)
    Is i an index on the priority queue?
    void
    decreaseKey(int i, K key)
    Decrease the key associated with index i to the specified value.
    void
    delete(int i)
    Delete the key associated with index i.
    int
    delMax()
    Delete a maximal key and return its associated index.
    private void
    exch(int i, int j)
     
    void
    increaseKey(int i, K key)
    Increase the key associated with index i to the specified value.
    void
    insert(int i, K key)
    Associate key with index i.
    boolean
    isEmpty()
    Is the priority queue empty?
    Iterator<Integer>
    iterator()
    Return an iterator that iterates over all of the elements on the priority queue in descending order.
    K
    keyOf(int i)
    Return the key associated with index i.
    private boolean
    less(int i, int j)
     
    static void
    main(String[] args)
     
    int
    maxIndex()
    Return the index associated with a maximal key.
    K
    maxKey()
    Return a minimal key.
    private void
    sink(int k)
     
    int
    size()
    Return the number of keys on the priority queue.
    private void
    swim(int k)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator