Priority Queues 1. In multi-user environments, a scheduler decides which of many available jobs to run at any time, when to switch to next etc. Think of computer systems, routers, printers etc.. Often, schedulers use a simple FIFO queue. This can be particularly bad if there is wide disparity in job sizes: 1-page vs. 100 page print job; 48 byte vs. 8K byte packet; telnet commands vs. big ftp. 2. A more refined form of the queue is called Priority Queue, in which jobs can be assigned priorities, and the queue pulls jobs out based on their priority. 3. Priority Queue ADT allows at least the following 2 operations: a. Insert an element; the key is the priority; b. DeleteMin; remove the element with the smallest key. (Think of priority as being the rank; smallest key is the most urgent job. One can also have a max priority queue.) 4. Sometimes, additional Operations: c. increaseKey d. decreaseKey e. remove an element (not min) 5. Naive Implementations: a. Linked list. Insert is O(1); deleteMin is O(n). b. Sorted linked list. Insert is O(n); deleteMin is O(1). c. Balanced tree. All in O(log n) but an overkill. 6. Heap-ordered Binary Tree (Min Heap) Such a common implementation of priority queue that heap is synonymous with priority queues. A heap is a COMPLETE binary tree (only vacancies are at the bottom level, and to the right). This full-ness ensures that a heap tree of height h has between 2^h and 2^(h+1) -1 nodes. Or, a heap with N nodes has height O(log N). 7. Heap Property. Not every complete binary tree is a heap. In order to become a heap, it must satisfy a heap-order property: for any node X, key(parent(X)) < key(X). (except the root, which has no parent) The motivation is obvious: we want to track the Min key, so best to keep it at the root. In order to restore this property, we must inductively preserve at all other nodes as well. Example: 13 13 21 16 21 16 24 31 19 68 6 31 19 68 65 26 32 65 26 32 A HEAP NOT a Heap! 8. By the heap-order property, the MIN key is always at the root. So, how do we implement the basic heap operations: insert, deleteMin. It's best to describe everything using two basic internal operations: percolateUp and percolateDown. The former is used for decreaseKey and insert. The latter is used for increaseKey and deleteMin. 9. decreaseKey (element, amount) (The operation assumes we know the location of e; heap does not have a find operation.) set key(e) -= amount percolateUp (e): while key(e) < key(parent(e)) swap e with its parent Simple Optimization: just move the parent down in the while loop; put e in its final/new place at the end of the loop. 10. increaseKey (e, amount) (The operation assumes we know the location of e; heap does not have a find operation.) set key(e) += amount percolateDown (e): while key(e) > key(some child of e) swap e with its smallest child Simple Optimization: just move the child up in the while loop; put e in its final/new place at the end of the loop. Examples: 11. insert and deleteMIn. insert: add new element as a new leaf; percolateUp (element) deleteMin: element at root is returned and deleted; swap root with the last leaf; percolateDown(new root) Since tree height is O(log N), and percolates traverse just one path in the tree, the cost is O(log N). More generally, the cost is O(height of tree). --------- 0. Array representation. Operations on Heaps are best visualized in the tree form, but the heap doesn't have to be implemented as a linked structure. The regularity of its shape makes it possible to encode the parent/children pointers implicitly as array locations. Example: 0 1 2 3 4 5 6 7 8 9 10 11 - A B C D E F G H I J K Then, children of node at location i are at locations 2i and 2i+1. Parent of node location j is \floor (j/2). 1. BuildHeap in O(n) time. Put the elements in given order in the array [1, n]. for (i = currentsize/2; i > 0; i--) percolateDown (i) 2. Analysis Tree has 2^i nodes at height h-i; root has height h percolateDown at height (h-i) takes h-i steps. So, total work is sum_{i=1}^h 2^i (h-i) S = h + 2(h-1) + 4(h-2) + .... 2^{h-1}*1 2S = 2h + 4(h-1) + .... 2^{h-1}*2 + 2^h * 1 Subtracting 1 from 2, we get S = -h + 2 + 4 + 8 + .... + 2^{h-1} + 2^h = -(h + 1) + (2^{h+1} -1 ) = O(n). 3. Other applications: a. Sorting: Heap Sort b. graph algorithms: Dijkstra, Prim etc. c. event simulation: Rather than simulate on ticks, use Heap to move from event to event. d. Selection: You have a list of job with deadlines, you want to find the top k (say, most urgent 100 jobs). Naively, it takes O(Nk). If we sort, we can read off from one end; bubble sort takes O(n^2); heapsort takes O(n log n); but sorting may be an overkill Algorithm 1. (Find k smallest elements) Take the first k elements off the list; build a MAX Heap. Read the next element y. Look at the root of the heap, r. r represents the LARGEST (lowest priority) element in heap. If y < r, kick off r and replace it with y; else kick off y. Each operation takes O(log k) --> total work O(N log k); actually O( k + (N-k) log k). (runtime memory is only O(k).) Algorithm 2: BuildHeap, and do k deleteMins. Time is O(N + k log N). 4. d-Heap. Instead of a binary tree, we use a d-ary tree. The basic heap operations essentially unchanged> percolateUp: if key(x) < key(parent(x)), swap with parent. O(log N) percolateDown: if key(x) > key of some child of x, swap with smallest child. O(d log N). In some applications, with many more inserts than deleteMins, this can be better. 5. Leftist Heaps. In some applications, pairs of heaps are repeatedly merged; spending linear time per merge out of the question; Leftist Heap supports Merge in same time as insert/deleteMin. Actually, insert and merge are special cases of Merge. Definition: There are many ways to define the height of a node in a tree. In L-Heap, the distance to the nearest non-full node is crucial. NPL: null path length. npl(v) = min distance to a descendant with 0 or 1 child. Leftist Heap Property: npl of left child >= npl of right child. 1 1 1 0 1* 0 0 0 0 1 0 0 0 Valid Leftist Heap Not a leftist heap 6. Lemma: A leftist tree with r nodes on its right path has at least 2^r -1 nodes. By induction. 7. Merging Let H1 and H2 be two heaps to be merged. Support root key of H2 >= root of H1. Recursively merge H2 with the RIGHT child of H1, and call the outout H. Make H the right child of H1. Swap the left and right children of H1's root to restore the leftist property. Ex. H1 H2 3 6 10 8 12 7 21 14 17 18 24 37 18 23 26 33 Merge: right child of H1 with H2, and call that H. H 6 12 7 18 24 8 37 33 17 18 26 Now, make H the right child of H1's root, and swap children to recove leftist property: 3 6 10 12 7 21 14 18 24 8 37 23 33 17 18 26 8. Skew Heaps. Just like leftist, but much simpler to implement. Use the Splay tree trick: worst case can be bad, but amortized case is fine. Swap left and right children every time (with one exception). 9. Binomial Queues. They make average insertion O(1) time; other operations remain O(log n).