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).
- Top-down heapify (sink). If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | /** * 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).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | /** * 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 | /************************************************************************* * 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 <tt>MaxPQ</tt> class represents a priority queue of generic keys. * It supports the usual <em>insert</em> and <em>delete-the-maximum</em> * 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 <em>insert</em> and <em>delete-the-maximum</em> operations take * logarithmic amortized time. * The <em>max</em>, <em>size</em>, and <em>is-empty</em> 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 <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of * <i>Algorithms, 4th Edition</i> 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<key>) 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 <tt>remove()</tt> 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 <tt>MaxPQ</tt> 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)"); }}</key> |
No comments:
Post a Comment