Priority Queue: Remove the largest / smallest item.
APIs:
PQ elementary implementations: (PQ with N items)
insert delete max max
Unordered array 1 N N
Ordered array N 1 1
Goal logN logN logN
Binary heap: Array representation of a heap-ordered complete binary tree.
Heap-ordered binary tree: Parent's key is no smaller than children's keys.
Binary heap properties:
- Largest key is A[1], which is the root of the binary tree (Don't use A[0]).
- Parent of node k is k / 2
- Children of node k is 2 * k and k * k + 1
We represent a heap of size N in private array pq[] of length N+1, with pq[0] unused and the heap in pq[1] through pq[N]. We access keys only through private helper functions less() and exch(). The heap operations that we consider work by first making a simple modification that could violate the heap condition, then traveling through the heap, modifying the heap as required to ensure that the heap condition is satisfied everywhere. We refer to this process as reheapifying, or restoring heap order.
- Bottom-up reheapify (swim). If the heap order is violated because a node's key becomes larger than that node's parents key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children (one is the old parent, and the other is smaller than the old parent because it was a child of that node) but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root.
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
- insert. We add the new item at the end of the array, increment the size of the heap, and then swim up through the heap with that item to restore the heap condition.
- Complexity O(logn).
/**
* Adds a new key to the priority queue.
* @param x the new key to add to the priority queue
*/
public void insert(Key x) {
// double size of array if necessary
if (N >= pq.length - 1) resize(2 * pq.length);
// add x, and percolate it up to maintain heap invariant
pq[++N] = x;
swim(N);
assert isMaxHeap();
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
- Remove the maximum. Get the root. Exchange the root with the node at end. Then sink it down.
- Complexity: O(logn).
/**
* Removes and returns a largest key on the priority queue.
* @return a largest key on the priority queue
* @throws java.util.NoSuchElementException if priority queue is empty.
*/
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null; // to avoid loiterig and help with garbage collection
if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}
Entire algorithms to build a binary heap:
/************************************************************************* * Compilation: javac MaxPQ.java * Execution: java MaxPQ < input.txt * * Generic max priority queue implementation with a binary heap. * Can be used with a comparator instead of the natural order, * but the generic Key type must still be Comparable. * * % java MaxPQ < tinyPQ.txt * Q X P (6 left on pq) * * We use a one-based array to simplify parent and child calculations. * * Can be optimized by replacing full exchanges with half exchanges * (ala insertion sort). * *************************************************************************/ import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /** * The MaxPQ class represents a priority queue of generic keys. * It supports the usual insert and delete-the-maximum * operations, along with methods for peeking at the maximum key, * testing if the priority queue is empty, and iterating through * the keys. * * This implementation uses a binary heap. * The insert and delete-the-maximum operations take * logarithmic amortized time. * The max, size, and is-empty operations take constant time. * Construction takes time proportional to the specified capacity or the number of * items used to initialize the data structure. *
* For additional documentation, see Section 2.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class MaxPQ<Key> implements Iterable<Key> { private Key[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator<Key> comparator; // optional Comparator /** * Initializes an empty priority queue with the given initial capacity. * @param initCapacity the initial capacity of the priority queue */ public MaxPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue. */ public MaxPQ() { this(1); } /** * Initializes an empty priority queue with the given initial capacity, * using the given comparator. * @param initCapacity the initial capacity of the priority queue * @param comparator the order in which to compare the keys */ public MaxPQ(int initCapacity, Comparator<Key> comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue using the given comparator. * @param comparator the order in which to compare the keys */ public MaxPQ(Comparator<Key> comparator) { this(1, comparator); } /** * Initializes a priority queue from the array of keys. * Takes time proportional to the number of keys, using sink-based heap construction. * @param keys the array of keys */ public MaxPQ(Key[] keys) { N = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < N; i++) pq[i+1] = keys[i]; for (int k = N/2; k >= 1; k--) sink(k); assert isMaxHeap(); } /** * Is the priority queue empty? * @return true if the priority queue is empty; false otherwise */ public boolean isEmpty() { return N == 0; } /** * Returns the number of keys on the priority queue. * @return the number of keys on the priority queue */ public int size() { return N; } /** * Returns a largest key on the priority queue. * @return a largest key on the priority queue * @throws java.util.NoSuchElementException if the priority queue is empty */ public Key max() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > N; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i <= N; i++) temp[i] = pq[i]; pq = temp; } /** * Adds a new key to the priority queue. * @param x the new key to add to the priority queue */ public void insert(Key x) { // double size of array if necessary if (N >= pq.length - 1) resize(2 * pq.length); // add x, and percolate it up to maintain heap invariant pq[++N] = x; swim(N); assert isMaxHeap(); } /** * Removes and returns a largest key on the priority queue. * @return a largest key on the priority queue * @throws java.util.NoSuchElementException if priority queue is empty. */ public Key delMax() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key max = pq[1]; exch(1, N--); sink(1); pq[N+1] = null; // to avoid loiterig and help with garbage collection if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMaxHeap(); return max; } /*********************************************************************** * Helper functions to restore the heap invariant. **********************************************************************/ private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } } /*********************************************************************** * Helper functions for compares and swaps. **********************************************************************/ private boolean less(int i, int j) { if (comparator == null) { return ((Comparable) pq[i]).compareTo(pq[j]) < 0; } else { return comparator.compare(pq[i], pq[j]) < 0; } } private void exch(int i, int j) { Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; } // is pq[1..N] a max heap? private boolean isMaxHeap() { return isMaxHeap(1); } // is subtree of pq[1..N] rooted at k a max heap? private boolean isMaxHeap(int k) { if (k > N) return true; int left = 2*k, right = 2*k + 1; if (left <= N && less(k, left)) return false; if (right <= N && less(k, right)) return false; return isMaxHeap(left) && isMaxHeap(right); } /*********************************************************************** * Iterator **********************************************************************/ /** * Returns an iterator that iterates over the keys on the priority queue * in descending order. * The iterator doesn't implement remove() since it's optional. * @return an iterator that iterates over the keys in descending order */ public Iterator<Key> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Key> { // create a new pq private MaxPQ<Key> copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { if (comparator == null) copy = new MaxPQ<Key>(size()); else copy = new MaxPQ<Key>(size(), comparator); for (int i = 1; i <= N; i++) copy.insert(pq[i]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Key next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMax(); } } /** * Unit tests the MaxPQ data type. */ public static void main(String[] args) { MaxPQ<String> pq = new MaxPQ<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } }
No comments:
Post a Comment