- A more efficient realization of a priority queue using a data structure called a binary heap. It performs both insertions and removals in logarithmic time
- Heap-Order Property: In a heap T , for every position p other than the root, the key stored at p is greater than or equal to the key stored at p’s parent.
- Complete Binary Tree Property: A heap T with height h is a complete binary tree if levels 0,1,2,…,h−1 of T have the maximal number of nodes possible and the remaining nodes at level h reside in the leftmost possible positions at that level.
- A heap T storing n entries has height h = ⌊log n⌋.
Implementing a Priority Queue with a Heap
public class HeapPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {
protected ArrayList<Entry<K, V>> heap = new ArrayList<>();
public HeapPriorityQueue(Comparator<K> c) { super(c); }
public HeapPriorityQueue() { super(); }
public HeapPriorityQueue(K[] keys, V[] values) {
super();
for (int i = 0; i < Math.min(keys.length, values.length); i++) {
heap.add(new PQEntry<>(keys[i], values[i]));
}
heapify();
}
protected void heapify() {
for (int i = heap.size() - 1; i >= 0; i--) {
downHeap(i);
}
}
@Override
public int size() { return heap.size(); }
@Override
public Entry<K, V> min() {
if (heap.isEmpty()) return null;
return heap.get(0);
}
protected void swap(int i, int j) {
Entry<K, V> temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
@Override
public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
checkKey(key);
Entry<K, V> newEntry = new PQEntry<>(key, value);
heap.add(newEntry);
upHeap(heap.size() - 1);
return newEntry;
}
protected void upHeap(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (compare(heap.get(index), heap.get(parentIndex)) >= 0) break;
swap(index, parentIndex);
index = parentIndex;
}
}
@Override
public Entry<K, V> removeMin() {
if (heap.isEmpty()) return null;
Entry<K, V> minEntry = heap.get(0);
swap(0, heap.size() - 1);
heap.remove(heap.size() - 1);
downHeap(0);
return minEntry;
}
protected void downHeap(int index) {
int leftChild = 2 * index + 1;
while ( leftChild < heap.size()) {
int next = leftChild;
int rightChild = leftChild + 1;
if (rightChild < heap.size()) {
next = (compare(heap.get(leftChild), heap.get(rightChild)) > 0) ? rightChild: leftChild;
}
if (compare(heap.get(index), heap.get(next)) <= 0) break;
swap(index, next);
index = next;
}
}
}
Adaptable Priority Queues
- remove, replaceKey, and replaceValue, O(log n)
- To allow an entry instance to encode a location within a priority queue, adding a third field that designates the current index of an entry within the array-based representation of the heap.
public interface AdaptablePriorityQueue<K, V> extends PriorityQueue<K, V>{
void remove(Entry<K, V> entry) throws IllegalArgumentException;
void replaceKey(Entry<K, V> entry, K key) throws IllegalArgumentException;
void replaceValue(Entry<K, V> entry , V value) throws IllegalArgumentException;
}
public class HeapAdaptablePriorityQueue<K, V> extends HeapPriorityQueue<K, V> implements AdaptablePriorityQueue<K, V>{
protected static class AdaptablePQEntry<K, V> extends PQEntry<K, V> {
private int index;
public AdaptablePQEntry(K k, V v, int index) {
super(k, v);
this.index = index;
}
public int getIndex() { return index; }
public void setIndex(int index) { this.index = index; }
}
public HeapAdaptablePriorityQueue() { super(); }
public HeapAdaptablePriorityQueue(Comparator<K> c) { super(c); }
protected AdaptablePQEntry<K, V> validate(Entry<K, V> entry) throws IllegalArgumentException {
if (!(entry instanceof AdaptablePQEntry)) throw new IllegalArgumentException("Invalid entry");
AdaptablePQEntry<K, V> temp = (AdaptablePQEntry<K, V>) entry;
int i = temp.getIndex();
if (i >= size() || compare(heap.get(i), temp) == 0) throw new IllegalArgumentException("Invalid entry");
return temp;
}
@Override
protected void swap(int i, int j) {
super.swap(i, j);
((AdaptablePQEntry<K, V>) heap.get(i)).setIndex(i);
((AdaptablePQEntry<K, V>) heap.get(j)).setIndex(j);
}
@Override
public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
checkKey(key);
Entry<K, V> newEntry = new AdaptablePQEntry<>(key, value, heap.size());
heap.add(newEntry);
upHeap(heap.size() - 1);
return newEntry;
}
protected void bubble(int index) {
int parentIndex = (index - 1) / 2;
if (index > 0 && compare(heap.get(index), heap.get(parentIndex)) > 0) upHeap(index);
else downHeap(index);
}
@Override
public void remove(Entry<K, V> entry) throws IllegalArgumentException {
AdaptablePQEntry<K, V> temp = validate(entry);
int index = temp.getIndex();
swap(index, heap.size() - 1);
heap.remove(size() - 1);
bubble(index);
}
@Override
public void replaceValue(Entry<K, V> entry, V value) throws IllegalArgumentException {
AdaptablePQEntry<K, V> temp = validate(entry);
AdaptablePQEntry<K, V> current = (AdaptablePQEntry<K, V>) heap.get(temp.getIndex());
current.setValue(value);
}
@Override
public void replaceKey(Entry<K, V> entry, K key) throws IllegalArgumentException {
checkKey(key);
AdaptablePQEntry<K, V> temp = validate(entry);
int index = temp.getIndex();
temp.setKey(key);
heap.set(index, temp);
bubble(index);
}
}
近期评论