Priority Queues - Heaps PDF

PRIORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: 1  PRIRORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: – insert – delete the...

PRIORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: 1  PRIRORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: – insert – delete the element with the minimum value (deleteMin) 2  PRIRORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: – insert – delete the element with the minimum value (deleteMin) we need to work with Comparable objects 3  PRIRORITY QUEUES - HEAPS A priority queue is a data structure that allows at least the following operations: – insert – delete the element with the minimum value (deleteMin) we need to work with Comparable objects – insert  enqueue – deleteMin  dequeue 4  PRIORITY QUEUES Possible implementations: – Linked Lists 5  PRIORITY QUEUES Possible implementations: – Linked Lists O(1) insertion time (insert at the front) O(N) deleteMin time 6  PRIORITY QUEUES Possible implementations: – Linked Lists O(1) insertion time (insert at the front) O(N) deleteMin time – Sorted Linked Lists O(N) insertion time (insert at the right place) O(1) deleteMin time (delete the first element) 7  PRIORITY QUEUES Possible implementations: – Linked Lists O(1) insertion time (insert at the front) O(N) deleteMin time – Sorted Linked Lists O(N) insertion time (insert at the right place) O(1) deleteMin time (delete the first element) – Binary Search Trees/ AVL Tree O(log N) insertion time O(log N ) deleteMin time (asymmetry, tree becomes right heavy!) 8  PRIORITY QUEUES Binary Search Trees look OK but are actually an overkill: – we do not need find or findMax operations – we do not need the pointers 9  PRIORITY QUEUES Binary Search Trees look OK but are actually an overkill: – we do not need find or findMax operations – we do not need the pointers A simplified binary tree called a HEAP is sufficient for implementing priority queues. 10  BINARY HEAPS Binary heaps are binary trees with two properties – Structure Property – Heap-order Property 11  BINARY HEAPS Structure Property – A heap is a binary tree that is completely filled with the possible exception of the bottom level, which is filled from left to right. 12  BINARY HEAPS Structure Property – A heap is a binary tree that is completely filled with the possible exception of the bottom level, which is filled from left to right. A A binary heap B C D E F G H I J 13  BINARY HEAPS Structure Property – Such a tree is known as a complete binary tree A B C D E F G H I J 14  BINARY HEAPS Other examples of complete binary trees A B C D E F G H I 15  BINARY HEAPS Other examples of complete binary trees A B C D E F G H I J K 16  BINARY HEAPS Examples of binary trees which are NOT COMPLETE A B C D E F G H I K 17  BINARY HEAPS Examples of binary trees which are NOT COMPLETE A B C D E G H I 18  BINARY HEAPS Examples of binary trees which are NOT COMPLETE A B C D E F G H J K 19  Perfect Binary Trees A perfect binary tree is a tree in which every node other than the leaves has two children and all the leafs are located at the bottom level. A A B C Perfect binary tree of height 0 Perfect binary tree of height 1 Total number of nodes A in a perfect binary tree of height h is 2h+1 – 1 B C Number of nodes at a level of depth d is 2d D E F G Perfect binary tree of height 2 Prove these! 20  COMPLETE BINARY TREES A complete binary tree of height h has between 2h and 2h+1-1 nodes. A A B C B C h-1 h E F G D E F G D H J K L M N O H I 2h+1- 2h-1+1-1 + 1 = 1 2h 21  COMPLETE BINARY TREES A complete binary tree of height h has between 2h and 2h+1-1 nodes. This implies that the height of a complete binary tree of N nodes is log2 N which is O(log N) 22  COMPLETE BINARY TREES Structure Property: – Since the complete binary tree is very regular, it can be represented with an array and does NOT require any pointers. 23  COMPLETE BINARY TREES Structure Property: – Since the complete binary tree is very regular, it can be represented with an array and does NOT require any pointers. – For an entry at array location i, (1 based) the children are at locations 2i and 2i+1 the parent (if any) is at location  i/2 . 24  COMPLETE BINARY TREES A B C D E F G H I J 25  COMPLETE BINARY TREES A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 26  COMPLETE BINARY TREES A B C D E F G H I J A 0 1 2 3 4 5 6 7 8 9 10 11 27  COMPLETE BINARY TREES A B C D E F G H I J A B C 0 1 2 3 4 5 6 7 8 9 10 11 28  COMPLETE BINARY TREES A B C D E F G H I J A B C D E 0 1 2 3 4 5 6 7 8 9 10 11 29  COMPLETE BINARY TREES A B C D E F G H I J A B C D E F G 0 1 2 3 4 5 6 7 8 9 10 11 30  COMPLETE BINARY TREES A B C D E F G H I J A B C D E F G H I 0 1 2 3 4 5 6 7 8 9 10 11 31  COMPLETE BINARY TREES A B C D E F G H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 32  COMPLETE BINARY TREES A B C D E F G H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 Note that we could also have used an array starting with 0 33  COMPLETE BINARY TREES A A possible problem is that the maximum array size needs to be known. B C Typically this can be handled by resizing D E F G H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 34  HEAP CLASS template class BinaryHeap { public: BinaryHeap( int capacity = 100 ); bool isEmpty( ) const; bool isFull( ) const; const Comparable & findMin( ) const; void insert( const Comparable & x ); void deleteMin( ); void deleteMin( Comparable & minItem ); void makeEmpty( ); private: int currentSize; // Number of elements in heap vector array; // The heap array void buildHeap( ); void percolateDown( int hole ); }; 35  HEAP CLASS template class BinaryHeap { public: BinaryHeap( int capacity = 100 ); bool isEmpty( ) const; bool isFull( ) const; const Comparable & findMin( ) const; void insert( const Comparable & x ); void deleteMin( ); void deleteMin( Comparable & minItem ); void makeEmpty( ); private: int currentSize; // Number of elements in heap vector array; // The heap array void buildHeap( ); void percolateDown( int hole ); }; 36  HEAP CLASS template class BinaryHeap { public: BinaryHeap( int capacity = 100 ); bool isEmpty( ) const; bool isFull( ) const; const Comparable & findMin( ) const; void insert( const Comparable & x ); void deleteMin( ); void deleteMin( Comparable & minItem ); void makeEmpty( ); private: int currentSize; // Number of elements in heap vector array; // The heap array void buildHeap( ); void percolateDown( int hole ); }; 37  HEAP CLASS template class BinaryHeap { public: BinaryHeap( int capacity = 100 ); bool isEmpty( ) const; bool isFull( ) const; const Comparable & findMin( ) const; void insert( const Comparable & x ); void deleteMin( ); void deleteMin( Comparable & minItem ); void makeEmpty( ); private: int currentSize; // Number of elements in heap vector array; // The heap array void buildHeap( ); void percolateDown( int hole ); }; 38  HEAP ORDER PROPERTY In addition to the structure property, we also need the heap-order property 39  HEAP ORDER PROPERTY In addition to the structure property, we also need the heap-order property – For every node X (except for the root), the key of the parent of X is smaller or equal to the key of X. 40  HEAP ORDER PROPERTY In addition to the structure property, we also need the heap-order property – For every node X (except for the root), the key of the parent of X is smaller or equal to the key of X. – The minimum element is at the root of the heap. 41  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 42  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 43  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 44  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 45  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 46  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 47  HEAP ORDER PROPERTY 13 21 16 24 31 19 100 65 26 32 Note that siblings are not ordered in any particular way! 48  HEAP ORDER PROPERTY 13 21 16 6 31 19 100 65 26 32 This complete tree does NOT have the heap-order property 49  BASIC HEAP OPERATIONS INSERT X – We create a hole in the next available location (to maintain the structure property) 50  BASIC HEAP OPERATIONS INSERT X – We create a hole in the next available location (to maintain the structure property) – Place X in the hole – If heap order property is violated keep on interchanging X with its parent until property is established 51  INSERTION 13 We want to insert 14 21 16 24 31 19 100 65 26 32 52  INSERTION 13 We want to insert 14 Create a hole and put 14 there 21 16 24 31 19 100 65 26 32 14 53  INSERTION 13 We want to insert 14 Create a hole and put 14 there 21 16 Heap property violated 24 31 19 100 65 26 32 14 54  INSERTION 13 We want to insert 14 Create a hole and put 14 there 21 16 Heap property violated 24 19 100 Exchange 14 65 26 32 31 55  INSERTION 13 We want to insert 14 Create a hole and put 14 there 21 16 Heap property violated 24 19 100 Exchange 14 Heap property violated 65 26 32 31 56  INSERTION 13 We want to insert 14 Create a hole and put 14 there 14 16 Heap property violated 24 21 19 100 Exchange Heap property violated 65 26 32 31 Exchange 57  INSERTION 13 We want to insert 14 Create a hole and put 14 there 14 16 Heap property violated 24 21 19 100 Exchange Heap property violated 65 26 32 31 Exchange Heap Property is now established 58  INSERTION 13 14 16 24 21 19 100 65 26 32 31 This strategy is called percolation or bubble-up 59  INSERTION 13 We want to insert 14 Create a hole 21 16 Heap property violated 24 31 19 100 65 26 32 14 0 1 2 3 4 5 6 7 8 9 10 11 13 21 16 24 31 19 100 65 26 32 Hole 60  INSERTION 13 21 16 24 19 100 65 26 32 31 14 0 1 2 3 4 5 6 7 8 9 10 11 13 21 16 24 19 100 65 26 32 31 Hole 61  INSERTION 13 16 24 21 19 100 65 26 32 31 14 0 1 2 3 4 5 6 7 8 9 10 11 13 16 24 21 19 100 65 26 32 31 Hole 62  INSERTION 13 We want to insert 14 14 16 24 21 19 100 65 26 32 31 14 Heap Property is now established 0 1 2 3 4 5 6 7 8 9 10 11 13 14 16 24 21 19 100 65 26 32 31 Hole 63  insert template void BinaryHeap::insert( const Comparable & x ) { if( isFull( ) ) throw Overflow( ); // Percolate up // Note that instead of swapping we move the hole up int hole = ++currentSize; for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 ) array[ hole ] = array[ hole / 2 ]; array[ hole ] = x; } 64  insert If an element needs to be percolated up d levels, the insert operation uses d+1 assignment operations 65  insert If an element needs to be percolated up d levels, the insert operation uses d+1 assignment operations – A swap would have required 3 assignments per swap, for a total 3d assignments for percolating d levels. void BinaryHeap::insert( const Comparable & x ) { if( isFull( ) ) throw Overflow( ); int hole = ++currentSize; for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 ) { tmp = array[ hole ] array[ hole ] = array[ hole / 2 ]; array[ hole / 2 ] = tmp; } } 66  insert If an element needs to be percolated up d levels, the insert operation uses d+1 assignment operations – A swap would have required 3 assignments per swap, for a total 3d swaps for percolating d levels. Thus insert takes O(log N) time at the maximum. – When the new element is also the new minimum. 67  DELETING THE MINIMUM Finding the minimum is easy, the hard part is removing it! 68  DELETING THE MINIMUM Finding the minimum is easy, the hard part is removing it! – Get the minimum value from the root 69  DELETING THE MINIMUM Finding the minimum is easy, the hard part is removing it! – Get the minimum value from the root – Since the new heap has one less element put the last element at the now vacant root. 70  DELETING THE MINIMUM Finding the minimum is easy, the hard part is removing it! – Get the minimum value from the root – Since the new heap has one less element put the last element at the now vacant root. – Percolate down until the heap property is established 71  DELETING THE MINIMUM 13 Remove 13 from the root 14 16 24 21 19 100 65 26 32 31 72  DELETING THE MINIMUM Remove 13 from the root 14 16 24 21 19 100 65 26 32 31 73  DELETING THE MINIMUM 31 Remove 13 from the root 14 16 Put the last element to the root and remove the last node 24 21 19 100 65 26 32 74  DELETING THE MINIMUM 14 Remove 13 from the root 31 16 Put the last element to the root and remove the last node 24 21 19 100 Percolate 31 one level down 65 26 32 75  DELETING THE MINIMUM 14 Remove 13 from the root 21 16 Put the last element to the root and remove the last node 24 31 19 100 Percolate 31 one level down Percolate 31 one level down 65 26 32 76  DELETING THE MINIMUM 14 Remove 13 from the root 21 16 Put the last element to the root and remove the last node 24 31 19 100 Percolate 31 one level down Percolate 31 one level down 65 26 32 Now heap-order property is re-established 77  DELETING THE MINIMUM 14 Remove 13 from the root 21 16 Put the last element to the root and remove the last node 24 31 19 100 Percolate 31 one level down Percolate 31 one level down 65 26 32 Now heap-order property is re-established One can also think of this as the hole at root moving down! 78  deleteMin() template void BinaryHeap::deleteMin( ) { if( isEmpty( ) ) throw Underflow( ); // move the last element to the first and shrink the array array[ 1 ] = array[ currentSize–– ]; percolateDown( 1 ); } 79  deleteMin(...) template void BinaryHeap::deleteMin( Comparable & minItem ) { if( isEmpty( ) ) throw Underflow( ); minItem = array[ 1 ]; array[ 1 ] = array[ currentSize-- ]; percolateDown( 1 ); } 80  (private) percolateDown template void BinaryHeap::percolateDown( int hole ) { int child; Comparable tmp = array[ hole ]; for( ; hole * 2