Implementing a Priority Queue with Heaps
"Learn about implementing a priority queue using heaps. Priority queues are essential data structures that maintain a special ordering property. The use of binary trees and heaps is explained in detail, focusing on maintaining shape and heap properties during insertions."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Implementing a Priority Queue Heaps
Priority Queues Recall: 3 Container Adapters Stack Queue Priority Queue implementation? Priority Queue Uses std::vector Maintains complete tree w/special ordering property Vector w/property is Heap
Binary Trees V > V <= V
Heaps (Max Heap) V <= V <= V
Binary Tree Heap vs. 6 13 9 3 3 9 1 3 1 6 7 7 1
Heap Shape Property A heap must be a complete binary tree This means the levels of the tree will always be filled from left-to-right Level 0 13 9 3 Level 1 6 7 1 Level 2
Insertion 13 9 3 6 7 1
Insertion 13 9 3 To maintain the Shape property, we must insert at the end of level 2 6 7 1 8
Insertion 13 9 3 But if we insert the 8 there the heap ordering property isn t maintained! 8 <= 3 6 7 1 8
Insertion 13 8 <= 13 9 8 So we do the only sensible thing and swap the values! 3 <= 8 6 7 1 3
Insertion 13 9 8 This strategy applies for more than one step , too 6 7 1 3 1 8
Insertion 13 18 <= 7 9 8 6 7 1 3 1 8
Insertion 13 18 <= 9 9 8 1 8 6 1 3 7
Insertion 13 1 8 18 <= 13 8 6 9 1 3 7
Insertion 18 13 <= 18 8 13 6 9 1 3 7
Insertion Done 18 The 13 node bubbled up from the bottom to its final position 8 13 This operation is known as upheap() 6 9 1 3 while n.data > parent(n).data: swap(n.data, parent(n).data) n = parent(n) if n == null: break 7
Removal 18 We can only remove from the top We need to maintain the shape property We need to maintain ordering property 8 13 6 9 1 3 7
Removal 7 Swap the root with the last We compare the node with its two children Choose the larger one and swap Repeat until in place 8 13 6 9 1 3 18 removed
Removal 13 Swap the root with the last We compare the node with its two children Choose the larger one and swap Repeat until in place 7 8 6 9 1 3 18 removed
Removal 13 Swap the root with the last We compare the node with its two children Choose the larger one and swap Repeat until in place 9 8 6 7 1 3 1 8 removed
Removal 13 The 7 node bubbled down from the top to its final position 9 8 This operation is known as downheap() 6 7 1 3 18 removed
Heaps Are Arrays 0 13 parent(i) = (i 1) / 2 9 8 1 2 left(i) = 2 * i + 1 right(i) = 2 * i + 2 6 4 7 1 3 3 5 6
Complete Binary Tree Why store tree in vector? 5 v[0] 1 3 v[2] v[1] 6 9 2 4 v[4] v[3] v[5] v[6] 8 7 0 parent (i) = p (i) = ? leftChild (i) = lc (i) = ? rightChild (i) = rc (i) = ? v[7] v[8] v[9]
Max and Min Heaps Max Heap property: ( nodes X) [ Value (X) >= Value (Child (X)) ] 55 40 52 30 50 15 11 10 10 25 5 20 22 (A) Maximum Heap (9 nodes) (B) Maximum Heap (4 nodes) 10 5 30 15 50 10 40 52 11 20 55 25 22 (C) Minimum Heap (9 nodes) (D) Minimum Heap (4 nodes)
priority_queue::push 63 63 v[0] v[0] 30 40 30 40 v[2] v[1] v[2] v[1] 25 8 38 10 25 8 38 10 v[4] v[3] v[5] v[6] v[4] v[3] v[5] v[6] 18 5 3 18 5 3 50 v[7] v[8] v[9] v[7] v[8] v[9] v[10] (a) (b) v.push_back (50);
Upheap (restore heap property) upHeap (v.size () 1); 63 63 63 v[0] v[0] . . . . . . v[0] 30 50 . . . 50 v[1] v[1] . . . . . . v[1] 50 . . . 30 30 v[4] v[4] v[4] 18 25 18 25 18 25 v[9] v[9] v[10] v[10] v[9] v[10] Step 1 Compare 50 and 25 (Exchange v[10] and v[4]) Step 2 Compare 50 and 30 (Exchange v[4] and v[1]) Step 3 Compare 50 and 63 (50 in correct location)
Push void PQ::push (const T& item) { v.push_back (item); upHeap (v.size () 1); }
upHeap (Helper Method) void PQ::upHeap (size_t pos) { T item = v[pos]; size_t i; // Move parent down for (i = pos; i != 0 && item > v[p (i)]; i = p (i)) v[i] = v[p (i)]; // swap unnecessary v[i] = item; }
priority_queue::pop v.front () = v.back (); v.pop_back (); 18 63 v[0] v[0] 30 40 30 40 v[2] v[2] v[1] v[1] 25 8 38 25 10 8 38 10 v[4] v[3] v[5] v[6] v[4] v[3] v[5] v[6] 63 18 5 3 18 5 3 v[7] v[8] v[9] v[7] v[8] v[9] After exchanging the root and last element in the heap Before a deletion
downHeap 40 40 v[0] v[0] . . . . . . 38 18 v[2] v[2] 8 18 8 38 v[5] v[6] v[5] v[6] Step 2: Exchange 18 and 38 Step 1: Exchange 18 and 40
Pop void PQ::pop () { v[0] = v.back (); v.pop_back (); // O (1) // Move elem down to proper place downHeap (0); }
downHeap (Helper Method) void PQ::downHeap (size_t pos) { // Move v[pos] down, max child up size_t i, mc; T val = v[pos]; for (i = pos; (mc = lc (i)) < v.size (); i = mc) { if (mc + 1 < v.size () && v[mc] < v[mc + 1]) ++mc; if (val ??) // Move child up if necessary else ? } // Place val in correct spot }
Heap Sort Overview Heaps O(N*lg (N)) sort in worst case Can use heaps to sort in two ways 1) pqSort Push all elements Pop and place in vector back to front Complexity? 2*Sum (i =1:N) [ lg(i) ]
Heap Sort Overview 2) True heap sort (better, why?) Heapify vector (O(N)) With STL assistance (make_heap) Roll our own buildHeap elemsToPlace = v.size () - 1 while (elemsToPlace > 0) Swap front and back of v --elemsToPlace Restore heap property at root (taking into consideration heap is one elem. smaller)
make_heap (STL) int arr[] { 50, 20, 75, 35, 25 }; // Header <algorithm> make_heap (arr, arr + 5); 75 35 50 25 20 Heapified Tree
buildHeap Potential algorithms (several don t work!) Call downHeap (0) N times Call downHeap (i) varying i from 0 to N-1 Call downHeap (i) varying i from N-1 to 0 Call upHeap (i) varying i from 0 to N-1 Call upHeap (i) varying i from N-1 to 0
buildHeap 9 17 12 20 30 50 60 65 4 19 Initial Vector Start at last internal node: position = ? 9 17 12 Then do downHeap (position) 20 30 50 60 65 4 19 adjustHeap() at 4 causes no changes (A)
buildHeap Contd 9 9 60 12 17 12 20 65 50 17 20 65 50 60 30 4 19 30 4 19 adjustHeap() at 2 moves 17 down (C) adjustHeap() at 3 moves 30 down (B) 65 9 60 50 60 65 20 30 19 17 20 30 50 17 12 4 9 12 4 19 adjustHeap() at 0 moves 9 down three levels (E) adjustHeap() at 1 moves 12 down two levels (D)
Heap Sorted Vector Now convert heap to sorted vector Swap front and back Decrease size of heap by 1 downheap (0)
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 10 9 6 7 2 4 5 3 Heap 10 Heap is in a[0..7] and the sorted region is empty 9 6 Swap front and back 7 2 4 5 3
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 3 9 6 7 2 4 5 10 Sorted Semiheap downHeap a[0..6] now represents a semiheap 3 a[7] is the sorted region 9 6 7 2 4 5
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 9 3 6 7 2 4 5 10 Sorted Becoming a Heap downHeap 9 3 6 7 2 4 5
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 9 7 6 3 2 4 5 10 Sorted Heap 9 7 6 3 2 4 5
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 5 7 6 3 2 4 9 Sorted 10 Semiheap downHeap 5 7 6 3 2 4
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 7 5 6 3 2 4 9 Sorted 10 Heap downHeap 7 5 6 3 2 4
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 4 5 6 3 2 7 9 10 Semiheap Sorted downHeap 4 5 6 3 2
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 6 5 4 3 2 7 9 10 Heap Sorted 6 5 4 3 2
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 2 5 4 3 6 7 Sorted 9 10 Semiheap downHeap 2 5 4 3
Transform a Heap Into a Sorted Array: Example 0 1 2 3 4 5 6 7 a[ ]: 5 2 4 3 6 7 Sorted 9 10 Becoming a Heap downHeap 5 2 4 3
Heap Sorted Vector 0 1 2 3 4 5 6 7 a[ ]: 5 3 4 2 6 7 Sorted 9 10 Heap 5 3 4 2
