Package edu.princeton.cs.algs4

Class IndexMaxPQ<Key extends Comparable<Key>>

  • Type Parameters:
    Key - the generic type of key on this priority queue
    All Implemented Interfaces:
    Iterable<Integer>
    public class IndexMaxPQ<Key extends Comparable<Key>>
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 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 Θ(log n) time in the worst case, where n is the number of elements in the priority queue. Construction takes time proportional to the specified capacity.

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

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

    • Constructor Detail

      • IndexMaxPQ

        public IndexMaxPQ​(int maxN)
        Initializes an empty indexed priority queue with indices between 0 and maxN - 1.
        Parameters:
        maxN - the keys on this priority queue are index from 0 to maxN - 1
        Throws:
        IllegalArgumentException - if maxN < 0

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Returns true if this priority queue is empty.
        Returns:
        true if this priority queue is empty; false otherwise

      • contains

        public boolean contains​(int i)
        Is i an index on this priority queue?
        Parameters:
        i - an index
        Returns:
        true if i is an index on this priority queue; false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN

      • size

        public int size()
        Returns the number of keys on this priority queue.
        Returns:
        the number of keys on this priority queue

      • insert

        public void insert​(int i,
                   Key key)
        Associate key with index i.
        Parameters:
        i - an index
        key - the key to associate with index i
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN
        IllegalArgumentException - if there already is an item associated with index i

      • maxIndex

        public int maxIndex()
        Returns an index associated with a maximum key.
        Returns:
        an index associated with a maximum key
        Throws:
        NoSuchElementException - if this priority queue is empty

      • maxKey

        public Key maxKey()
        Returns a maximum key.
        Returns:
        a maximum key
        Throws:
        NoSuchElementException - if this priority queue is empty

      • delMax

        public int delMax()
        Removes a maximum key and returns its associated index.
        Returns:
        an index associated with a maximum key
        Throws:
        NoSuchElementException - if this priority queue is empty

      • keyOf

        public Key keyOf​(int i)
        Returns the key associated with index i.
        Parameters:
        i - the index of the key to return
        Returns:
        the key associated with index i
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN
        NoSuchElementException - no key is associated with index i

      • changeKey

        public void changeKey​(int i,
                      Key key)
        Change the key associated with index i to the specified value.
        Parameters:
        i - the index of the key to change
        key - change the key associated with index i to this key
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN

      • increaseKey

        public void increaseKey​(int i,
                        Key key)
        Increase the key associated with index i to the specified value.
        Parameters:
        i - the index of the key to increase
        key - increase the key associated with index i to this key
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN
        IllegalArgumentException - if key <= keyOf(i)
        NoSuchElementException - no key is associated with index i

      • decreaseKey

        public void decreaseKey​(int i,
                        Key key)
        Decrease the key associated with index i to the specified value.
        Parameters:
        i - the index of the key to decrease
        key - decrease the key associated with index i to this key
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN
        IllegalArgumentException - if key >= keyOf(i)
        NoSuchElementException - no key is associated with index i

      • delete

        public void delete​(int i)
        Remove the key on the priority queue associated with index i.
        Parameters:
        i - the index of the key to remove
        Throws:
        IllegalArgumentException - unless 0 <= i < maxN
        NoSuchElementException - no key is associated with index i

      • iterator

        public Iterator<Integer> iterator()
        Returns an iterator that iterates over the keys on the priority queue in descending order. The iterator doesn't implement remove() since it's optional.
        Specified by:
        iterator in interface Iterable<Key extends Comparable<Key>>
        Returns:
        an iterator that iterates over the keys in descending order

      • main

        public static void main​(String[] args)
        Unit tests the IndexMaxPQ data type.
        Parameters:
        args - the command-line arguments