Cpt S 223, Fall 2007 Copyright: Washington State University 1Priority Queues & HeapsReading: Weiss, Chapter 6Cpt S 223, Fall 2007 Copyright: Washington State University 2Priority Queues• Printer jobs need prioritization• Eg., – Dynamic Job Queue: • 100 1 page jobs• 1 1000 page job• Idea: give the 100 page jobs higher priority to avoid starvation• Need data structure that implement such priority queuesCpt S 223, Fall 2007 Copyright: Washington State University 3Priority Queues: Basic Operations• Insert (x)• x = DeleteMin()– Return the next minimum entry in the queue• Alternative: x = DeleteMax()– Return the next maximum entry in the queueCpt S 223, Fall 2007 Copyright: Washington State University 4Priority Queues: Inefficient Implementations• Linked list– Insert (x) • Append to list • O(1) time– X = DeleteMin()• Search for the minimum element and return• O(n) time– Alternatively, keep the linked list sorted in reverse order• Insert(x) will take O(n) time• DeleteMin() will take O(1) timeCpt S 223, Fall 2007 Copyright: Washington State University 5Inefficient Implementations• Binary Search Tree– Insert (x)• O(log n) average– DeleteMin()• O(log n) average– Inserts could be random, but deletions are not!Cpt S 223, Fall 2007 Copyright: Washington State University 6Binary Heaps• Binary heaps are a basic implementation of priority queues• Basic idea:– Maintain a “complete binary tree” with the minimum element always at the top of the tree (ie., root)– Easy picking of the minimum– Inserts cost but try to keep it a low overheadCpt S 223, Fall 2007 Copyright: Washington State University 7Binary Heaps: Definition• A binary heap should satisfy the following two properties:1. Structure Property2. Heap Order PropertyCpt S 223, Fall 2007 Copyright: Washington State University 8Binary Heaps: Structure Property• A binary heap is a “complete binary tree”• ie., all leaves are full except possibly the last level• Height h has between 2hto 2h+1-1 nodes• H = O(log n) i 2i 2i+1Cpt S 223, Fall 2007 Copyright: Washington State University 9Binary Heaps: Heap Property• For any subtree within the binary tree the element at the top is the smallest– ie., any node should be smaller than all of its descendants– For every node X, the key in the parent of X is smaller than (or equal to) the key in X• This is called a MinHeapCpt S 223, Fall 2007 Copyright: Washington State University 10Heap PropertyBinary HeapNot a Heap!Cpt S 223, Fall 2007 Copyright: Washington State University 11Class Interface for HeapCpt S 223, Fall 2007 Copyright: Washington State University 12Basic Heap Insertion1321 163124 9 6865 26 32• Insert (14)• Pick the next available spot• But 14 cannot go to that spot because of heap property• So percolate up until the spot is found• Move all nodes on the way downCpt S 223, Fall 2007 Copyright: Washington State University 13Insert (14)14Cpt S 223, Fall 2007 Copyright: Washington State University 14Insert CodeCpt S 223, Fall 2007 Copyright: Washington State University 15deleteMinPercolate downCpt S 223, Fall 2007 Copyright: Washington State University 16 Cpt S 223, Fall 2007 Copyright: Washington State University 17Cpt S 223, Fall 2007 Copyright: Washington State University 18Cpt S 223, Fall 2007 Copyright: Washington State University 19More MinHeap Operations• decreaseKey(p,∆)– System admin can use– Percolate up• increaseKey(p,∆)– Percolate down• remove(p)– decreaseKey(p,infinity)– deleteMin()Cpt S 223, Fall 2007 Copyright: Washington State University 20buildHeap()• Do n insertions– Cost: O(n log n)• Alternative strategy:– Randomly build a tree with all the elements– Adjust using percolateDown() on all internal nodes starting at the bottom-most level Cpt S 223, Fall 2007 Copyright: Washington State University 21Initial TreeAfter percolateDown(7)After percolateDown(5)After percolateDown(6)Cpt S 223, Fall 2007 Copyright: Washington State University 22After percolateDown(3)After percolateDown(1)After percolateDown(4)After percolateDown(2)Cpt S 223, Fall 2007 Copyright: Washington State University 23Complexity of buildHeap()• Run-time = sum of all heights of all nodes• Let us call this sum S• Theorem:– For the perfect binary tree of height h containing 2h+1-1 nodes, S=2h+1-1-(h+1)– ==> S = O(n)Cpt S 223, Fall 2007 Copyright: Washington State University 24An Application: The Selection Problem• Given a list of n elements, find the kthelement• Simple but less efficient algorithm– Sort the list (O(n log n))– Pick the kthelement• A better approach– Use MinHeapCpt S 223, Fall 2007 Copyright: Washington State University 25Selection using a MinHeap• Input: n elements• An O(n log n) Algorithm:1. buildHeap(n) ==> O(n)2. Perform k deleteMin() operations ==> O(k log n)3. Report the kthdeleteMin output– Total run-time = O(n + k log n)– Note: If k = O(n/log n) then the run-time becomes O(n)Cpt S 223, Fall 2007 Copyright: Washington State University 26Other Types of Heaps• d-Heaps– Generalization of binary heaps (ie., 2-Heaps)• Leftist Heaps– Supports merging of two heaps in o(m+n) time (ie., sub-linear)• Skew Heaps– O(log n) amortized run-timeCpt S 223, Fall 2007 Copyright: Washington State University 27Binomial HeapsCpt S 223, Fall 2007 Copyright: Washington State University 28(Amortized) Run-time Per OperationO(log n)O(log n)O(1) Binomial HeapO(log n)O(log n)O(log n)Skew HeapO(log n)O(log n)O(log n)Leftist HeapO(n)O(log n)O(1)Binary heapMergeDeleteMinInsertCpt S 223, Fall 2007 Copyright: Washington State University 29Binomial Heap• A forest of heap-ordered trees• The structural property of each heap-ordered tree is different from binary heap’• Each heap-ordered tree has a “binomial tree” structureCpt S 223, Fall 2007 Copyright: Washington State University 30A “Binomial Tree”• A binomial tree of height k:– Has 2knodes– The number of nodes at depth d is the binomial co-efficient ( )kdd=0d=1d=2d=3(30)(31)(32)(33)Cpt S 223, Fall 2007 Copyright: Washington State University 31A Binomial Heap w/ n=31 nodesn = 31 = (1 1 1 1 1)2B0B1B2B3B4B2B2Cpt S 223, Fall 2007 Copyright: Washington State University 32Binomial Heap Structure: Idea• A heap’s structure should be valid for any value of n (ie., number of nodes)• If a binomial heap is to be constructed as a forest of binomial trees then:– It