public class IndexMultiwayMinPQ<Key> extends Object implements Iterable<Integer>
Constructor and Description |
---|
IndexMultiwayMinPQ(int N,
Comparator<Key> C,
int D)
Initializes an empty indexed priority queue with indices between
0 to N-1
Worst case is O(n) |
IndexMultiwayMinPQ(int N,
int D)
Initializes an empty indexed priority queue with indices between
0 to N-1
Worst case is O(n) |
Modifier and Type | Method and Description |
---|---|
void |
changeKey(int i,
Key key)
Changes the key associated with index i to the given key
If the given key is greater, Worst case is O(d*log-d(n))
If the given key is lower, Worst case is O(log-d(n))
|
boolean |
contains(int i)
Does the priority queue contains the index i ?
Worst case is O(1)
|
void |
decreaseKey(int i,
Key key)
Decreases the key associated with index i to the given key
Worst case is O(log-d(n))
|
void |
delete(int i)
Deletes the key associated to the given index
Worst case is O(d*log-d(n))
|
int |
delMin()
Deletes the minimum key
Worst case is O(d*log-d(n))
|
void |
increaseKey(int i,
Key key)
Increases the key associated with index i to the given key
Worst case is O(d*log-d(n))
|
void |
insert(int i,
Key key)
Associates a key with an index
Worst case is O(log-d(n))
|
boolean |
isEmpty()
Whether the priority queue is empty
Worst case is O(1)
|
Iterator<Integer> |
iterator()
Gets an Iterator over the indexes in the priority queue in ascending order
The Iterator does not implement the remove() method
iterator() : Worst case is O(n)
next() : Worst case is O(d*log-d(n))
hasNext() : Worst case is O(1)
|
Key |
keyOf(int i)
Gets the key associated with index i
Worst case is O(1)
|
int |
minIndex()
Gets the index associated with the minimum key
Worst case is O(1)
|
Key |
minKey()
Gets the minimum key currently in the queue
Worst case is O(1)
|
int |
size()
Number of elements currently on the priority queue
Worst case is O(1)
|
public IndexMultiwayMinPQ(int N, int D)
0
to N-1
Worst case is O(n)N
- number of keys in the priority queue, index from 0
to N-1
D
- dimension of the heapIllegalArgumentException
- if N < 0
IllegalArgumentException
- if D < 2
public IndexMultiwayMinPQ(int N, Comparator<Key> C, int D)
0
to N-1
Worst case is O(n)N
- number of keys in the priority queue, index from 0
to N-1
D
- dimension of the heapC
- a Comparator over the keysIllegalArgumentException
- if N < 0
IllegalArgumentException
- if D < 2
public boolean isEmpty()
public boolean contains(int i)
i
- an indexIllegalArgumentException
- if the specified index is invalidpublic int size()
public void insert(int i, Key key)
i
- an indexkey
- a Key associated with iIllegalArgumentException
- if the specified index is invalidIllegalArgumentException
- if the index is already in the queuepublic int minIndex()
NoSuchElementException
- if the priority queue is emptypublic Key minKey()
NoSuchElementException
- if the priority queue is emptypublic int delMin()
NoSuchElementException
- if the priority queue is emptypublic Key keyOf(int i)
i
- an indexIllegalArgumentException
- if the specified index is invalidIllegalArgumentException
- if the index is not in the queuepublic void changeKey(int i, Key key)
i
- an indexkey
- the key to associate with iIllegalArgumentException
- if the specified index is invalidIllegalArgumentException
- if the index has no key associated withpublic void decreaseKey(int i, Key key)
i
- an indexkey
- the key to associate with iIllegalArgumentException
- if the specified index is invalidNoSuchElementException
- if the index has no key associated withIllegalArgumentException
- if the given key is greater than the current keypublic void increaseKey(int i, Key key)
i
- an indexkey
- the key to associate with iIllegalArgumentException
- if the specified index is invalidNoSuchElementException
- if the index has no key associated withIllegalArgumentException
- if the given key is lower than the current keypublic void delete(int i)
i
- an indexIllegalArgumentException
- if the specified index is invalidNoSuchElementException
- if the given index has no key associated with