CMSC 341Priority QueuesPriority Queue ApplicationsPossible ImplementationsMin Binary HeapMin Binary Heap PerformanceMin Binary Heap PropertiesHeap is a Complete Binary TreeWhich satisfies the properties of a Heap?Min BinaryHeap DefinitionMin BinaryHeap ImplementationInsert OperationMin BinaryHeap Insert (cont.)Insert 14Deletion OperationMin BinaryHeap Deletion(cont.)MinBinaryHeap percolateDown(cont.)deleteMindeleteMin (cont.)Constructing a Min BinaryHeapConstructing a Min BinaryHeap(cont.)Performance of ConstructionPerformance of Construction (cont.)Heap SortLimitationsLeftist Min HeapLeftist TreeSlide 28MergeMerge (cont.)Slide 31Slide 32Slide 33Slide 34Student ExerciseStudent Exercise Final ResultMin Leftist Heap OperationsLH ConstructCMSC 341Binary HeapsPriority Queues8/3/2007UMBC CSMC 341 PQueue2Priority QueuesPriority: some property of an object that allows it to be prioritized with respect to other objects of the same typeMin Priority Queue: homogeneous collection of Comparables with the following operations (duplicates are allowed). Smaller value means higher priority.void insert (Comparable x)void deleteMin( )void deleteMin ( Comparable min)Comparable findMin( ) Construct from a set of initial valuesboolean isEmpty( )boolean isFull( ) void makeEmpty( )8/3/2007UMBC CSMC 341 PQueue3Priority Queue ApplicationsPrinter management: The shorter document on the printer queue, the higher its priority.Jobs queue within an operating system:Users’ tasks are given priorities. System priority high.SimulationsThe time an event “happens” is its priority.Sorting (heap sort)An elements “value” is its priority.8/3/2007UMBC CSMC 341 PQueue4Possible ImplementationsUse a sorted list. Sorted by priority upon insertion.findMin( ) --> list.front( )insert( ) --> list.insert( )deleteMin( ) --> list.erase( list.begin( ) )Use ordinary BSTfindMin( ) --> tree.findMin( )insert( ) --> tree.insert( )deleteMin( ) --> tree.delete( tree.findMin( ) )Use balanced BSTguaranteed O(lg n) for Red-Black8/3/2007UMBC CSMC 341 PQueue5Min Binary HeapA min binary heap is a complete binary tree with the further property that at every node neither child is smaller than the value in that node (or equivalently, both children are at least as large as that node). This property is called a partial ordering.As a result of this partial ordering, every path from the root to a leaf visits nodes in a non-decreasing order.What other properties of the Min Binary Heap result from this property?8/3/2007UMBC CSMC 341 PQueue6Min Binary Heap PerformancePerformance (n is the number of elements in the heap)construction O( n )findMin O( 1 )insert O( lg n )deleteMin O( lg n )Heap efficiency results, in part, from the implementationConceptually a complete binary treeImplementation in an array/vector (in level order) with the root at index 18/3/2007UMBC CSMC 341 PQueue7Min Binary Heap PropertiesFor a node at index iits left child is at index 2iits right child is at index 2i+1its parent is at index i/2No pointer storageFast computation of 2i and i/2 by bit shiftingi << 1 = 2ii >> 1 = i/28/3/2007UMBC CSMC 341 PQueue8Heap is a Complete Binary Tree8/3/2007UMBC CSMC 341 PQueue9Which satisfies the properties of a Heap?8/3/2007UMBC CSMC 341 PQueue10Min BinaryHeap Definition public class BinaryHeap<AnyType extends Comparable<? super AnyType>>{ public BinaryHeap( ) { /* See online code */ } public BinaryHeap( int capacity ){ /* See online code */ } public BinaryHeap( AnyType [ ] items ){/* Figure 6.14 */ } public void insert( AnyType x ) { /* Figure 6.8 */ } public AnyType findMin( ) { /* TBD */ } public AnyType deleteMin( ) { /* Figure 6.12 */ } public boolean isEmpty( ) { /* See online code */ } public void makeEmpty( ) { /* See online code */ } private static final int DEFAULT_CAPACITY = 10; private int currentSize; // Number of elements in heap private AnyType [ ] array; // The heap array private void percolateDown( int hole ){/* Figure 6.12 */ } private void buildHeap( ) { /* Figure 6.14 */ } private void enlargeArray(int newSize){/* code online */}}8/3/2007UMBC CSMC 341 PQueue11Min BinaryHeap Implementationpublic AnyType findMin( ){if ( isEmpty( ) ) throw Underflow( ); return array[1];}8/3/2007UMBC CSMC 341 PQueue12Insert OperationMust maintainCBT property (heap shape): Easy, just insert new element at “the end” of the arrayMin heap orderCould be wrong after insertion if new element is smaller than its ancestorsContinuously swap the new element with its parent until parent is not greater than itCalled sift up or percolate upPerformance of insert is O( lg n ) in the worst case because the height of a CBT is O( lg n )8/3/2007UMBC CSMC 341 PQueue13Min BinaryHeap Insert (cont.)/** * Insert into the priority queue, maintaining heap order. * Duplicates are allowed. * @param x the item to insert. */ public void insert( AnyType x ){ if( currentSize == array.length - 1 ) enlargeArray( array.length * 2 + 1 ); // Percolate up int hole = ++currentSize; for( ; hole > 1&& x.compareTo(array[hole/2]) < 0; hole/=2 ) array[ hole ] = array[ hole / 2 ]; array[ hole ] = x;}8/3/2007UMBC CSMC 341 PQueue14Insert 148/3/2007UMBC CSMC 341 PQueue15Deletion OperationStepsRemove min element (the root)Maintain heap shapeMaintain min heap orderTo maintain heap shape, actual node removed is “last one” in the arrayReplace root value with value from last node and delete last nodeSift-down the new root value Continually exchange value with the smaller child until no child is smaller.8/3/2007UMBC CSMC 341 PQueue16Min BinaryHeap Deletion(cont.)/** * Remove the smallest item from the priority queue. * @return the smallest item, or throw UnderflowException, if empty. */ public AnyType deleteMin( ) { if( isEmpty( ) ) throw new UnderflowException( ); AnyType minItem = findMin( ); array[ 1 ] = array[ currentSize-- ]; percolateDown( 1 ); return minItem; }8/3/2007UMBC CSMC 341 PQueue17MinBinaryHeap percolateDown(cont.) /** * Internal method to percolate down in the heap. * @param hole the index at which the percolate begins. */private void percolateDown( int hole ){ int child; AnyType
View Full Document