CMSC 341 Binary Heaps Priority Queues Priority 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 8 3 2007 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 UMBC CSMC 341 PQueue 2 Priority Queue Applications Printer management Jobs queue within an operating system Users tasks are given priorities System priority high Simulations The shorter document on the printer queue the higher its priority The time an event happens is its priority Sorting heap sort 8 3 2007 An elements value is its priority UMBC CSMC 341 PQueue 3 Possible Implementations Use a sorted list Sorted by priority upon insertion Use ordinary BST findMin list front insert list insert deleteMin list erase list begin findMin tree findMin insert tree insert deleteMin tree delete tree findMin Use balanced BST 8 3 2007 guaranteed O lg n for Red Black UMBC CSMC 341 PQueue 4 Min 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 nondecreasing order What other properties of the Min Binary Heap result from this property 8 3 2007 UMBC CSMC 341 PQueue 5 Min Binary Heap Performance Performance n is the number of elements in the heap construction findMin insert deleteMin O n O 1 O lg n O lg n Heap efficiency results in part from the implementation 8 3 2007 Conceptually a complete binary tree Implementation in an array vector in level order with the root at index 1 UMBC CSMC 341 PQueue 6 Min 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 8 3 2007 UMBC CSMC 341 PQueue 7 Heap is a Complete Binary Tree 8 3 2007 UMBC CSMC 341 PQueue 8 Which satisfies the properties of a Heap 8 3 2007 UMBC CSMC 341 PQueue 9 Min 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 2007 UMBC CSMC 341 PQueue 10 Min BinaryHeap Implementation public AnyType findMin if isEmpty throw Underflow return array 1 8 3 2007 UMBC CSMC 341 PQueue 11 Insert 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 8 3 2007 UMBC CSMC 341 PQueue 12 Min 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 2007 UMBC CSMC 341 PQueue 13 Insert 14 8 3 2007 UMBC CSMC 341 PQueue 14 Deletion 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 8 3 2007 Continually exchange value with the smaller child until no child is smaller UMBC CSMC 341 PQueue 15 Min 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 2007 UMBC CSMC 341 PQueue 16 MinBinaryHeap 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 8 3 2007 UMBC CSMC 341 PQueue 17 deleteMin 8 3 2007 UMBC CSMC 341 PQueue 18 deleteMin cont 8 3 2007 UMBC CSMC 341 PQueue 19 Constructing 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 8 3 2007 UMBC CSMC 341 PQueue 20 Constructing a Min BinaryHeap cont Construct the binary heap given an array of items public BinaryHeap AnyType items currentSize items length array AnyType new Comparable currentSize 2 11 10 int i 1 for AnyType item items array i item buildHeap Establish heap order property from an arbitrary arrangement of items Runs in linear time private void buildHeap for int i currentSize 2 i 0 i percolateDown i 8 3 2007 UMBC CSMC 341 PQueue 21 Performance of Construction A CBT has 2h 1 nodes on level h 1 On level h l at most 1 swap is needed per node On level h 2 at most 2 swaps are needed On level 0 at most h swaps are needed Number of swaps S 2h 0 2h 1 1 2h 2 2 20 h h h h i 2 h i h 2 i 2 i i 0 h 2h 1 1 i i 0 i 0 h 1 2h 1 2 2h 1 h h …