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.

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.
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.
static void	main(String[] args)
int	maxIndex()	Return the index associated with a maximal key.
K	maxKey()	Return a minimal key.
int	size()	Return the number of keys on the priority queue.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

IndexMaxPQ

public IndexMaxPQ(int NMAX)

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

Throws:

IllegalArgumentException - if NMAX < 0

Method Details

isEmpty

public boolean isEmpty()

Is the priority queue empty?

contains

public boolean contains(int i)

Is i an index on the priority queue?

Throws:

IndexOutOfBoundsException - unless (0 <= i < NMAX)

size

public int size()

Return the number of keys on the priority queue.

insert

public void insert(int i,
 K key)

Associate key with index i.

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

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

maxIndex

public int maxIndex()

Return the index associated with a maximal key.

Throws:

NoSuchElementException - if priority queue is empty.

maxKey

public K maxKey()

Return a minimal key.

Throws:

NoSuchElementException - if priority queue is empty.

delMax

public int delMax()

Delete a maximal key and return its associated index.

Throws:

NoSuchElementException - if priority queue is empty.

keyOf

public K keyOf(int i)

Return the key associated with index i.

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

NoSuchElementException - no key is associated with index i

change

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

Deprecated.

Replaced by changeKey()

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

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

NoSuchElementException - no key is associated with index i

changeKey

public void changeKey(int i,
 K key)

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

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

NoSuchElementException - no key is associated with index i

increaseKey

public void increaseKey(int i,
 K key)

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

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

IllegalArgumentException - if key ≤ key associated with index i

NoSuchElementException - no key is associated with index i

decreaseKey

public void decreaseKey(int i,
 K key)

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

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

IllegalArgumentException - if key ≥ key associated with index i

NoSuchElementException - no key is associated with index i

delete

public void delete(int i)

Delete the key associated with index i.

Throws:

IndexOutOfBoundsException - unless 0 <= i < NMAX

NoSuchElementException - no key is associated with index i

iterator

public Iterator<Integer> iterator()

Return an iterator that iterates over all of the elements on the priority queue in descending order.

The iterator doesn't implement remove() since it's optional.

Specified by:

iterator in interface Iterable<K extends Comparable<? super K>>

main

public static void main(String[] args)