Key
- the generic type of key on this priority queuepublic class IndexMinPQ<Key extends Comparable<Key>> extends Object implements Iterable<Integer>
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 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 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, contains, 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 |
---|
IndexMinPQ(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 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()
Returns true if this priority queue is empty.
|
Iterator<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(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 this priority queue.
|
public IndexMinPQ(int maxN)
0
and maxN - 1
.maxN
- the keys on this priority queue are index from 0
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
.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 minIndex()
NoSuchElementException
- if this priority queue is emptypublic Key minKey()
NoSuchElementException
- if this priority queue is emptypublic int delMin()
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
NoSuchElementException
- no key is associated with index i
@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 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 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 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)
IndexMinPQ
data type.args
- the command-line arguments