Understanding Priority Queues and Heaps

Priority queues differ from regular queues by maintaining an ordering of items based on priority rather than first-in-first-out. Items in a priority queue are assigned priority values and the highest priority item is removed first. Different data structures can be used to efficiently insert and remove items from a priority queue while ensuring operations are performed in a timely manner.

• Priority Queues
• Data Structures
• Heaps
• Priority
• Efficient Operations

ldon Follow

Uploaded on Sep 10, 2024 | 0 Views

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.

Presentation Transcript

1. Priority Queues and Heaps

2. A queue should implement at least the first two of these operations: insert insert item at the back of the queue remove remove an item from the front peek return the item at the front of the queue without removing it It is assumed that these operations will be implemented efficiently That is, in constant time October 2004 John Edgar 2

3. 4 0 18 25 1 2 3 5 4 Either with an array 2 5 6 7 6 front back 4 Or with a linked list 7 3 October 2004 John Edgar 3

4. Queues are first-in first-out (FIFO) Priority queues are a fancier type of queue Maintains an ordering of items in the queue, not necessarily first-in first-out October 2004 John Edgar 4

5. 4 5 1 2 6 3 September 2004 John Edgar 5

6. Items in a priority queue are given a priority value Which could be numerical or something else The highest priority item is removed first Uses include System requests Data structure to support Dijkstra s Algorithm September 2004 John Edgar 6

7. Can items be inserted and removed efficiently from a priority queue? Using an array, or Using a linked list? Note that items are not removed based on the order in which they are inserted Now we ll see how we can do these efficiently (using a different data structure) September 2004 John Edgar 7

8. Items in a priority queue have a priority Not necessarily numerical Could be lowest first or highest first The highest priority item is removed first Priority queue operations Insert Remove in priority queue order Both operations should be performed in at most O(log n) time October 2004 John Edgar 8

9. September 2004 John Edgar 9

10. Items have to be removed in priority order This can only be done efficiently if the items are ordered in some way One option would be to use a balanced binary search tree Binary search trees are fully ordered and insertion and removal can be implemented in O(log n) time Some operations (e.g. removal) are complex Although operations are O(logn) they require quite a lot of structural overhead There is a much simpler binary tree solution October 2004 John Edgar 10

11. A heap is binary tree with two properties Heaps are complete All levels, except the bottom, are completely filled in The leaves on the bottom level are as far to the left as possible. Heaps are partially ordered The value of a node is at least as large as its children s values, for a maxheap or The value of a node is no greater than its children s values, for a minheap October 2004 John Edgar 11

12. complete binary trees incomplete binary trees October 2004 John Edgar 12

13. 98 86 41 13 65 32 29 9 10 44 23 21 17 Heaps are not fully ordered, an inorder traversal would result in: 9, 13, 10, 86, 44, 65, 23, 98, 21, 32, 17, 41, 29 October 2004 John Edgar 13

14. A heap can implement a priority queue The item at the top of the heap must always be the highest priority value Because of the partial ordering property Implement priority queue operations: Insertions insert an item into a heap Removal remove and return the heap s root For both operations preserve the heap property October 2004 John Edgar 14

15. September 2004 John Edgar 15

16. Heaps can be implemented using arrays There is a natural method of indexing tree nodes Index nodes from top to bottom and left to right as shown on the right Because heaps are complete binary trees there can be no gaps in the array 0 2 1 3 4 5 6 October 2004 John Edgar 16

17. It will be necessary to find the index of the parents of a node Or the children of a node The array is indexed from 0 to n 1 Each level's nodes are indexed from: 2level 1 to 2level+1 2 (where the root is level 0) The children of a node i, are the array elements indexed at 2i + 1 and 2i+ 2 The parent of a node i, is the array element indexed at floor((i 1) / 2) October 2004 John Edgar 17

18. 0 98 1 2 86 41 Heap 3 4 5 6 13 65 32 29 7 8 9 10 11 12 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 value 98 86 41 13 65 32 29 9 10 44 23 21 17 Underlying Array October 2004 John Edgar 18

19. September 2004 John Edgar 19

20. On insertion the heap properties have to be maintained; remember that A heap is a complete binary tree and A partially ordered binary tree There are two general strategies that could be used to maintain the heap properties Make sure that the tree is complete and then fix the ordering or Make sure the ordering is correct first Which is better? October 2004 John Edgar 20

21. The insertion algorithm first ensures that the tree is complete Make the new item the first available (left-most) leaf on the bottom level i.e. the first free element in the underlying array Fix the partial ordering Compare the new value to its parent Swap them if the new value is greater than the parent Repeat until this is not the case Referred to as bubbling up, or trickling up October 2004 John Edgar 21

22. Insert 81 98 86 41 13 65 32 29 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 value 98 86 41 13 65 32 29 9 10 44 23 21 17 October 2004 John Edgar 22

23. 81 is less than 98 so finished Insert 81 98 41 81 86 13 65 32 29 81 41 9 10 44 23 21 17 81 29 (13-1)/2 = 6 index index index index 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 11 10 11 10 11 10 11 12 12 12 12 13 13 13 13 value value value value 98 86 41 98 86 41 98 86 41 98 86 81 13 13 13 13 65 32 29 65 32 29 65 32 81 65 32 41 9 9 9 9 10 44 23 21 10 44 23 21 10 44 23 21 10 44 23 21 17 17 17 17 81 29 29 October 2004 John Edgar 23

24. September 2004 John Edgar 24

25. Make a temporary copy of the roots data Similarly to the insertion algorithm, first ensure that the heap remains complete Replace the root node with the right-most leaf i.e. the highest (occupied) index in the array Swap the new root with its largest valued child until the partially ordered property holds i.e. bubble down Return the root s data October 2004 John Edgar 25

26. Remove (root) 98 86 41 13 65 32 29 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 value 98 86 41 13 65 32 29 9 10 44 23 21 17 October 2004 John Edgar 26

27. replace root with right-most leaf Remove (root) 98 17 86 41 13 65 32 29 9 10 44 23 21 17 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 98 86 17 86 41 41 13 13 65 65 32 32 29 29 9 9 10 10 44 44 23 23 21 21 17 October 2004 John Edgar 27

28. ? ? swap with larger child Remove (root) 17 86 86 17 41 13 65 32 29 9 10 44 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 17 86 86 17 41 41 13 13 65 65 32 32 29 29 9 9 10 10 44 44 23 23 21 21 children of root: 2*0+1, 2*0+2 = 1, 2 October 2004 John Edgar 28

29. swap with larger child Remove (root) 86 ? ? 17 65 41 13 65 17 32 29 9 10 44 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 86 86 65 17 41 41 13 13 65 17 32 32 29 29 9 9 10 10 44 44 23 23 21 21 children of 1: 2*1+1, 2*1+2 = 3, 4 October 2004 John Edgar 29

30. swap with larger child Remove (root) 86 65 41 13 17 44 32 29 ? ? 9 10 44 17 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 86 65 86 65 41 41 13 13 17 44 32 32 29 29 9 9 10 10 44 17 23 23 21 21 children of 4: 2*4+1, 2*4+2 = 9, 10 October 2004 John Edgar 30

31. September 2004 John Edgar 31

32. Helper functions are usually written for preserving the heap property bubbleUp ensures that the heap property is preserved from the start node up to the root bubbleDown ensures that the heap property is preserved from the start node down to the leaves These functions may be implemented recursively or iteratively October 2004 John Edgar 32

33. Go to terminal October 2004 John Edgar 33

34. October 2004 John Edgar 34

35. Lab next week October 2004 John Edgar 35

36. Lab next week October 2004 John Edgar 36

37. For both insertion and removal the heap performs at most height swaps For insertion at most height comparisons To bubble up the array For removal at most height* 2 comparisons To bubble down the array (have to compare two children) Height of a complete binary tree is log2(n) Both insertion and removal are therefore O(logn) October 2004 John Edgar 37

38. September 2004 John Edgar 38

39. Observation 1: Removal of a node from a heap can be performed in O(logn) time Observation 2: Nodes are removed in order Conclusion: Removing all of the nodes one by one would result in sorted output Analysis: Removal ofall the nodes from a heap is a O(n*logn) operation October 2004 John Edgar 39

40. A heap can be used to return sorted data In O(n*logn) time However, we can t assume that the data to be sorted just happens to be in a heap! Aha! But we can put it in a heap. Inserting an item into a heap is a O(logn) operation so inserting n items is O(n*logn) But we can do better than just repeatedly calling the insertion algorithm October 2004 John Edgar 40

41. To create a heap from an unordered array repeatedly call bubbleDown Any subtree in a heap is itself a heap Call bubbleDown on elements in the upper of the array Start with index n/2 and work up to index 0 i.e. from the last non-leaf node to the root bubbleDown does not need to be called on the lower half of the array (the leaves) Since bubbleDown restores the partial ordering from any given node down to the leaves October 2004 John Edgar 41

42. Assume unsorted input is contained in an array as shown here (indexed from top to bottom and left to right) 0 89 2 29 23 1 3 6 4 5 36 48 94 13 7 8 9 10 11 12 27 70 76 37 42 58 October 2004 John Edgar 42

43. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 2 29 23 1 3 6 4 5 36 48 94 94 13 7 8 9 10 11 12 27 70 76 37 42 42 58 58 October 2004 John Edgar 43

44. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 23 1 3 6 4 5 36 48 76 94 13 7 8 9 10 11 12 27 70 76 48 37 37 42 58 October 2004 John Edgar 44

45. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 23 1 bubbleDown(3) 3 6 4 5 36 70 76 94 13 7 8 9 10 11 12 27 27 70 36 48 37 42 58 October 2004 John Edgar 45

46. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 23 94 29 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 13 13 70 76 94 23 58 7 8 9 10 11 12 27 36 48 37 42 58 23 October 2004 John Edgar 46

47. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 76 94 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 70 76 29 48 13 13 58 bubbleDown(1) 7 8 9 10 11 12 27 36 48 29 37 42 23 October 2004 John Edgar 47

48. n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 94 bubbleDown(4) 2 94 89 76 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 70 13 13 48 58 bubbleDown(1) bubbleDown(0) 7 8 9 10 11 12 27 36 37 29 42 23 October 2004 John Edgar 48

49. bubbleDown is called on half the array The cost for bubbleDown is O(height) It would appear that heapify cost is O(n*logn) In fact the cost is O(n) The analysis is complex but bubbleDown is only called on n/2 nodes and mostly on sub-trees October 2004 John Edgar 49

50. Heapify the array Repeatedly remove the root After each removal swap the root with the last element in the tree The array is divided into a heap part and a sorted part At the end of the sort the array will be sorted in reverse order October 2004 John Edgar 50

Load More ...