Class IndexMinPQ<Key extends java.lang.Comparable<Key>>

java.lang.Object

IndexMinPQ<Key>

All Implemented Interfaces:

java.lang.Iterable<java.lang.Integer>

public class IndexMinPQ<Key extends java.lang.Comparable<Key>>
extends java.lang.Object
implements java.lang.Iterable<java.lang.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 keys 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.

This implementation uses a binary heap along with an array to associate keys with integers in the given range. 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.

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

Constructor Summary

Constructors

Constructor and Description
IndexMinPQ(int NMAX) Initializes an empty indexed priority queue with indices between 0 and NMAX-1.

Method Summary

Methods

Modifier and Type	Method and Description
void	change(int i, Key key) Deprecated. Replaced by changeKey()
void	changeKey(int i, Key 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, Key key) Decrease the key associated with index i to the specified value.
void	delete(int i) Remove the key associated with index i.
int	delMin() Removes a minimum key and returns its associated index.
void	increaseKey(int i, Key key) Increase the key associated with index i to the specified value.
void	insert(int i, Key key) Associates key with index i.
boolean	isEmpty() Is the priority queue empty?
java.util.Iterator<java.lang.Integer>	iterator() Returns an iterator that iterates over the keys on the priority queue in ascending order.
Key	keyOf(int i) Returns the key associated with index i.
static void	main(java.lang.String[] args) Unit tests the IndexMinPQ data type.
int	minIndex() Returns an index associated with a minimum key.
Key	minKey() Returns a minimum key.
int	size() Returns the number of keys on the priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

IndexMinPQ

public IndexMinPQ(int NMAX)

Initializes an empty indexed priority queue with indices between 0 and NMAX-1.

Parameters:

NMAX - the keys on the priority queue are index from 0 to NMAX-1

Throws:

java.lang.IllegalArgumentException - if NMAX < 0

Method Detail

isEmpty

public boolean isEmpty()

Is the priority queue empty?

Returns:

true if the priority queue is empty; false otherwise

contains

public boolean contains(int i)

Is i an index on the priority queue?

Parameters:

i - an index

Throws:

java.lang.IndexOutOfBoundsException - unless (0 ≤ i < NMAX)

size

public int size()

Returns the number of keys on the priority queue.

Returns:

the number of keys on the priority queue

insert

public void insert(int i,
          Key key)

Associates key with index i.

Parameters:

i - an index

key - the key to associate with index i

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.util.IllegalArgumentException - if there already is an item associated with index i

minIndex

public int minIndex()

Returns an index associated with a minimum key.

Returns:

an index associated with a minimum key

Throws:

java.util.NoSuchElementException - if priority queue is empty

minKey

public Key minKey()

Returns a minimum key.

Returns:

a minimum key

Throws:

java.util.NoSuchElementException - if priority queue is empty

delMin

public int delMin()

Removes a minimum key and returns its associated index.

Returns:

an index associated with a minimum key

Throws:

java.util.NoSuchElementException - if 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:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.util.NoSuchElementException - no key is associated with index i

change

@Deprecated
public void change(int i,
                     Key key)

Deprecated. Replaced by changeKey()

Change the key associated with index i to the specified value.

Parameters:

i - the index of the key to change

key - change the key assocated with index i to this key

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

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 assocated with index i to this key

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.util.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 assocated with index i to this key

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.lang.IllegalArgumentException - if key ≥ key associated with index i

java.util.NoSuchElementException - no key is associated with index i

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 assocated with index i to this key

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.lang.IllegalArgumentException - if key ≤ key associated with index i

java.util.NoSuchElementException - no key is associated with index i

delete

public void delete(int i)

Remove the key associated with index i.

Parameters:

i - the index of the key to remove

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ i < NMAX

java.util.NoSuchElementException - no key is associated with index i

iterator

public java.util.Iterator<java.lang.Integer> iterator()

Returns an iterator that iterates over the keys on the priority queue in ascending order. The iterator doesn't implement remove() since it's optional.

Specified by:

iterator in interface java.lang.Iterable<java.lang.Integer>

Returns:

an iterator that iterates over the keys in ascending order

main

public static void main(java.lang.String[] args)

Unit tests the IndexMinPQ data type.