Key
- the generic type of key on this priority queuepublic class IndexMaxPQ<Key extends Comparable<Key>> extends Object implements Iterable<Integer>
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.
Constructor and Description |
---|
IndexMaxPQ(int maxN)
Initializes an empty indexed priority queue with indices between
0
and maxN - 1 . |
Modifier and Type | Method and Description |
---|---|
void |
change(int i,
Key key)
Deprecated.
Replaced by
changeKey(int, Key) . |
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 this 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 on the priority queue 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()
Returns true if this priority queue is empty.
|
Iterator<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(String[] args)
Unit tests the
IndexMaxPQ data type. |
int |
maxIndex()
Returns an index associated with a maximum key.
|
Key |
maxKey()
Returns a maximum key.
|
int |
size()
Returns the number of keys on this priority queue.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEach, spliterator
public IndexMaxPQ(int maxN)
0
and maxN - 1
.maxN
- the keys on this priority queue are index from 0
to maxN - 1
IllegalArgumentException
- if maxN < 0
public boolean isEmpty()
true
if this priority queue is empty;
false
otherwisepublic boolean contains(int i)
i
an index on this priority queue?i
- an indextrue
if i
is an index on this priority queue;
false
otherwiseIllegalArgumentException
- unless 0 <= i < maxN
public int size()
public void insert(int i, Key key)
i
- an indexkey
- the key to associate with index i
IllegalArgumentException
- unless 0 <= i < maxN
IllegalArgumentException
- if there already is an item
associated with index i
public int maxIndex()
NoSuchElementException
- if this priority queue is emptypublic Key maxKey()
NoSuchElementException
- if this priority queue is emptypublic int delMax()
NoSuchElementException
- if this priority queue is emptypublic Key keyOf(int i)
i
.i
- the index of the key to returni
IllegalArgumentException
- unless 0 <= i < maxN
NoSuchElementException
- no key is associated with index i
public void changeKey(int i, Key key)
i
to the specified value.i
- the index of the key to changekey
- change the key associated with index i
to this keyIllegalArgumentException
- unless 0 <= i < maxN
@Deprecated public void change(int i, Key key)
changeKey(int, Key)
.i
to the specified value.i
- the index of the key to changekey
- change the key associated with index i
to this keyIllegalArgumentException
- unless 0 <= i < maxN
public void increaseKey(int i, Key key)
i
to the specified value.i
- the index of the key to increasekey
- increase the key associated with index i
to this keyIllegalArgumentException
- unless 0 <= i < maxN
IllegalArgumentException
- if key <= keyOf(i)
NoSuchElementException
- no key is associated with index i
public void decreaseKey(int i, Key key)
i
to the specified value.i
- the index of the key to decreasekey
- decrease the key associated with index i
to this keyIllegalArgumentException
- unless 0 <= i < maxN
IllegalArgumentException
- if key >= keyOf(i)
NoSuchElementException
- no key is associated with index i
public void delete(int i)
i
.i
- the index of the key to removeIllegalArgumentException
- unless 0 <= i < maxN
NoSuchElementException
- no key is associated with index i
public Iterator<Integer> iterator()
remove()
since it's optional.public static void main(String[] args)
IndexMaxPQ
data type.args
- the command-line arguments