Package algs24

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

java.lang.Object
algs24.IndexMinPQ<K>
All Implemented Interfaces:
Iterable<Integer>
public class IndexMinPQ<K extends Comparable<? super K>> extends Object implements Iterable<Integer>
The IndexMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum 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 minimum key, testing if the priority queue is empty, and iterating through the keys.

The insert, delete-the-minimum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, min-index, min-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 
    IndexMinPQ.HeapIterator
     

  • Field Summary

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    IndexMinPQ(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
    delMin()
    Delete a minimal key and return its associated index.
    private void
    exch(int i, int j)
     
    private boolean
    greater(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 ascending order.
    K
    keyOf(int i)
    Return the key associated with index i.
    static void
    main(String[] args)
     
    int
    minIndex()
    Return the index associated with a minimal key.
    K
    minKey()
    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