public class HeapAdaptablePriorityQueue<K,V> extends HeapPriorityQueue<K,V> implements AdaptablePriorityQueue<K,V>
| Modifier and Type | Class and Description |
|---|---|
protected static class |
HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V>
Extension of the PQEntry to include location information.
|
AbstractPriorityQueue.PQEntry<K,V>heap| Constructor and Description |
|---|
HeapAdaptablePriorityQueue()
Creates an empty adaptable priority queue using natural ordering of keys.
|
HeapAdaptablePriorityQueue(Comparator<K> comp)
Creates an empty adaptable priority queue using the given comparator to order keys.
|
| Modifier and Type | Method and Description |
|---|---|
protected void |
bubble(int j)
Restores the heap property by moving the entry at index j upward/downward.
|
Entry<K,V> |
insert(K key,
V value)
Inserts a key-value pair and return the entry created.
|
void |
remove(Entry<K,V> entry)
Removes the given entry from the priority queue.
|
void |
replaceKey(Entry<K,V> entry,
K key)
Replaces the key of an entry.
|
void |
replaceValue(Entry<K,V> entry,
V value)
Replaces the value of an entry.
|
protected void |
swap(int i,
int j)
Exchanges the entries at indices i and j of the array list.
|
protected HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V> |
validate(Entry<K,V> entry)
Validates an entry to ensure it is location-aware.
|
downheap, hasLeft, hasRight, heapify, left, main, min, parent, removeMin, right, size, upheapcheckKey, compare, isEmptyclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitisEmpty, min, removeMin, sizepublic HeapAdaptablePriorityQueue()
public HeapAdaptablePriorityQueue(Comparator<K> comp)
comp - comparator defining the order of keys in the priority queueprotected HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V> validate(Entry<K,V> entry) throws IllegalArgumentException
entry - an entry instanceIllegalArgumentException - if the given entry was not validprotected void swap(int i,
int j)
swap in class HeapPriorityQueue<K,V>protected void bubble(int j)
public Entry<K,V> insert(K key, V value) throws IllegalArgumentException
insert in interface PriorityQueue<K,V>insert in class HeapPriorityQueue<K,V>key - the key of the new entryvalue - the associated value of the new entryIllegalArgumentException - if the key is unacceptable for this queuepublic void remove(Entry<K,V> entry) throws IllegalArgumentException
remove in interface AdaptablePriorityQueue<K,V>entry - an entry of this priority queueIllegalArgumentException - if e is not a valid entry for the priority queue.public void replaceKey(Entry<K,V> entry, K key) throws IllegalArgumentException
replaceKey in interface AdaptablePriorityQueue<K,V>entry - an entry of this priority queuekey - the new keyIllegalArgumentException - if e is not a valid entry for the priority queue.public void replaceValue(Entry<K,V> entry, V value) throws IllegalArgumentException
replaceValue in interface AdaptablePriorityQueue<K,V>entry - an entry of this priority queuevalue - the new valueIllegalArgumentException - if e is not a valid entry for the priority queue.