Question? Leave a message!




Priority Queues

Priority Queues
RyanCanon Profile Pic
RyanCanon,United Arab Emirates,Teacher
Published Date:20-07-2017
Website URL
Comment
Binary Heaps Priority QueuesPriority Queues  Priority: some property of an object that allows it to be prioritized with respect to other objects of the same type  Min 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 values  boolean isEmpty( )  boolean isFull( )  void makeEmpty( ) www.ThesisScientist.comPriority Queue Applications  Printer 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.  Simulations  The time an event “happens” is its priority.  Sorting (heap sort)  An elements “value” is its priority. www.ThesisScientist.comPossible Implementations  Use a sorted list. Sorted by priority upon insertion.  findMin( ) list.front( )  insert( ) list.insert( )  deleteMin( ) list.erase( list.begin( ) )  Use ordinary BST  findMin( ) tree.findMin( )  insert( ) tree.insert( )  deleteMin( ) tree.delete( tree.findMin( ) )  Use balanced BST  guaranteed O(lg n) for Red-Black www.ThesisScientist.comMin Binary Heap  A 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? www.ThesisScientist.comMin Binary Heap Performance  Performance (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 implementation  Conceptually a complete binary tree  Implementation in an array/vector (in level order) with the root at index 1 www.ThesisScientist.comMin Binary Heap Properties  For a node at index i  its left child is at index 2i  its right child is at index 2i+1  its parent is at index i/2  No pointer storage  Fast computation of 2i and i/2 by bit shifting i 1 = 2i i 1 = i/2 www.ThesisScientist.comHeap is a Complete Binary Tree www.ThesisScientist.comWhich satisfies the properties of a Heap? www.ThesisScientist.comMin BinaryHeap Definition public class BinaryHeapAnyType 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 / www.ThesisScientist.comMin BinaryHeap Implementation public AnyType findMin( ) if ( isEmpty( ) ) throw Underflow( ); return array1; www.ThesisScientist.comInsert Operation  Must maintain  CBT property (heap shape):  Easy, just insert new element at “the end” of the array  Min heap order  Could be wrong after insertion if new element is smaller than its ancestors  Continuously swap the new element with its parent until parent is not greater than it  Called sift up or percolate up  Performance of insert is O( lg n ) in the worst case because the height of a CBT is O( lg n ) www.ThesisScientist.comMin 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(arrayhole/2) 0; hole/=2 ) array hole = array hole / 2 ; array hole = x; www.ThesisScientist.comInsert 14 www.ThesisScientist.comDeletion Operation  Steps  Remove min element (the root)  Maintain heap shape  Maintain min heap order  To maintain heap shape, actual node removed is “last one” in the array  Replace root value with value from last node and delete last node  Sift-down the new root value  Continually exchange value with the smaller child until no child is smaller. www.ThesisScientist.comMin 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; www.ThesisScientist.comMinBinaryHeap 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 tmp = array hole ; for( ; hole 2 = currentSize; hole = child ) child = hole 2; if( child = currentSize && array child + 1 .compareTo( array child ) 0 ) child++; if( array child .compareTo( tmp ) 0 ) array hole = array child ; else break; array hole = tmp; www.ThesisScientist.comdeleteMin www.ThesisScientist.comdeleteMin (cont.) www.ThesisScientist.comConstructing a Min BinaryHeap  A BH can be constructed in O(n) time.  Suppose we are given an array of objects in an arbitrary order. Since it’s an array with no holes, it’s already a CBT. It can be put into heap order in O(n) time.  Create the array and store n elements in it in arbitrary order. O(n) to copy all the objects.  Heapify the array starting in the “middle” and working your way up towards the root for (int index = n/2 ; index 0; index) percolateDown( index ); www.ThesisScientist.com