public class IndexMaxPQ<Key extends java.lang.Comparable<Key>> extends java.lang.Object implements java.lang.Iterable<java.lang.Integer>
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 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.
For additional documentation, see Section 2.4 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
IndexMaxPQ(int NMAX)
Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
|
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 |
delMax()
Removes a maximum 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)
Associate 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 descending order.
|
Key |
keyOf(int i)
Returns the key associated with index i.
|
static void |
main(java.lang.String[] args)
Unit tests the IndexMaxPQ data type.
|
int |
maxIndex()
Returns an index associated with a maximum key.
|
Key |
maxKey()
Return a maximum key.
|
int |
size()
Returns the number of keys on the priority queue.
|
public IndexMaxPQ(int NMAX)
NMAX
- the keys on the priority queue are index from 0 to NMAX-1java.lang.IllegalArgumentException
- if NMAX < 0public boolean isEmpty()
public boolean contains(int i)
i
- an indexjava.lang.IndexOutOfBoundsException
- unless (0 ≤ i < NMAX)public int size()
public void insert(int i, Key key)
i
- an indexkey
- the key to associate with index ijava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXjava.util.IllegalArgumentException
- if there already is an item associated with index ipublic int maxIndex()
java.util.NoSuchElementException
- if priority queue is emptypublic Key maxKey()
java.util.NoSuchElementException
- if priority queue is emptypublic int delMax()
java.util.NoSuchElementException
- if priority queue is emptypublic Key keyOf(int i)
i
- the index of the key to returnjava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXjava.util.NoSuchElementException
- no key is associated with index i@Deprecated public void change(int i, Key key)
i
- the index of the key to changekey
- change the key assocated with index i to this keyjava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXpublic void changeKey(int i, Key key)
i
- the index of the key to changekey
- change the key assocated with index i to this keyjava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXpublic void increaseKey(int i, Key key)
i
- the index of the key to increasekey
- increase the key assocated with index i to this keyjava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXjava.lang.IllegalArgumentException
- if key ≤ key associated with index ijava.util.NoSuchElementException
- no key is associated with index ipublic void decreaseKey(int i, Key key)
i
- the index of the key to decreasekey
- decrease the key assocated with index i to this keyjava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXjava.lang.IllegalArgumentException
- if key ≥ key associated with index ijava.util.NoSuchElementException
- no key is associated with index ipublic void delete(int i)
i
- the index of the key to removejava.lang.IndexOutOfBoundsException
- unless 0 ≤ i < NMAXjava.util.NoSuchElementException
- no key is associated with index ipublic java.util.Iterator<java.lang.Integer> iterator()
iterator
in interface java.lang.Iterable<java.lang.Integer>
public static void main(java.lang.String[] args)