Download as PDF, PPTX
![ADT: Priority Queue A Priority Queue models a collection that is not First-In-First-Out (FIFO), but instead most- important-in-first-out. Example: Hospital emergency room. The patient who is most in danger is treated first. Items in a priority queue are comparable, and the comparison determines priority. Often this is done by inserting items as a pair: (item, priority). Operations: insert(item, [priority]) – adds an item to the queue with a given priority deleteMin() – removes and returns the most-important item in the priority queue peekMin() – returns the most-important item in the priority queue without removal (This is a min priority queue. You can also have a max priority queue by swapping min/max.) CSE 373 SU 18 – BEN JONES 5](https://image.slidesharecdn.com/lecture-10-241204123607-60e248a9/75/Introduction-to-the-logic-programing-prolog-5-2048.jpg)
![In Place Heap Sort CSE 373 SP 18 - KASEY CHAMPION 25 public void inPlaceHeapSort(collection) { E[] heap = buildHeap(collection) for (n) output[n – i - 1] = removeMin(heap) } Worst case runtime? Best case runtime? Average runtime? O(nlogn) O(nlogn) O(nlogn) 0 1 2 3 4 5 6 7 8 9 15 17 16 18 20 22 14 4 2 1 Heap Sorted Items Current Item Complication: final array is reversed! - Run reverse afterwards (O(n)) - Use a max heap - Reverse compare function to emulate max heap](https://image.slidesharecdn.com/lecture-10-241204123607-60e248a9/75/Introduction-to-the-logic-programing-prolog-25-2048.jpg)
Introduction to the logic programing prolog
- 1. Priority Queues and Heaps DataStructures and Algorithms CSE 373 SU 18 – BEN JONES 1
- 2. Warm Up CSE 373SU 18 – BEN JONES 2 We have seen several data structures that can implement the Dictionary ADT so far: Arrays, Binary (AVL) Trees, and Hash Tables. 1. Discuss with your neighbors the relative merits of each approach? 2. Is there any reason to choose an AVL Tree Dictionary over a Hash Table?
- 3. BST vs HashTable BST ADVANTAGES CSE 373 SU 18 – BEN JONES & CSE 373 SU 17 LILIAN DE GREEF 3 Extra Operations: Get keys in sorted order, ordering statistics (min-key, max-key, etc.), “closest” elements, range queries O(log n) worst case runtime guaranteed, better than O(n) for hash tables Easier to implement HASH TABLE ADVANTAGES O(1) Average Case Operations Array Lookups can be an order of magnitude faster than following references
- 4. How can wetrack the “biggest” thing? CSE 373 SU 18 – BEN JONES 4 Last class, a question was raised: couldn’t we guarantee O(1) operations if we kept track of the largest cluster in a hash table?
- 5. ADT: Priority Queue APriority Queue models a collection that is not First-In-First-Out (FIFO), but instead most- important-in-first-out. Example: Hospital emergency room. The patient who is most in danger is treated first. Items in a priority queue are comparable, and the comparison determines priority. Often this is done by inserting items as a pair: (item, priority). Operations: insert(item, [priority]) – adds an item to the queue with a given priority deleteMin() – removes and returns the most-important item in the priority queue peekMin() – returns the most-important item in the priority queue without removal (This is a min priority queue. You can also have a max priority queue by swapping min/max.) CSE 373 SU 18 – BEN JONES 5
- 6. Implementing Priority Queue IdeaDescription removeMin() runtime peekMin() runtime insert() runtime Unsorted ArrayList Linear collection of values, stored in an Array, in order of insertion O(n) O(n) O(1) Unsorted LinkedList Linear collection of values, stored in Nodes, in order of insertion O(n) O(n) O(1) Sorted ArrayList Linear collection of values, stored in an Array, priority order maintained as items are added O(1) O(1) O(n) Sorted Linked List Linear collection of values, stored in Nodes, priority order maintained as items are added O(1) O(1) O(n) Binary Search Tree Hierarchical collection of values, stored in Nodes, priority order maintained as items are added O(n) O(n) O(n) AVL tree Balanced hierarchical collection of values, stored in Nodes, priority order maintained as items are added O(logn) O(logn) O(logn) CSE 373 SP 18 - KASEY CHAMPION 6
- 7. Heaps Priority QueueData Structure CSE 373 SU 18 – BEN JONES 7
- 8. Binary Heap A typeof tree with new set of invariants 1. Binary Tree: every node has at most 2 children 2. Heap: every node is smaller than its child CSE 373 SP 18 - KASEY CHAMPION 8 8 9 10 2 4 5 3 6 7 1 3. Structure: Each level is “complete” meaning it has no “gaps” - Heaps are filled up left to right 22 36 47 2 4 8 9 10 3 1 5
- 9. Self Check -Are these valid heaps? CSE 373 SP 18 - KASEY CHAMPION 9 Binary Heap Invariants: 1. Binary Tree 2. Heap 3. Complete 2 3 5 7 8 4 9 11 10 5 9 8 6 7 4 3 7 1 6 INVALID INVALID VALID
- 10. Implementing peekMin() CSE 373SP 18 - KASEY CHAMPION 10 4 5 8 7 10 2 9 11 13
- 11. Implementing removeMin() CSE 373SP 18 - KASEY CHAMPION 11 4 5 8 7 10 2 9 11 13 Removing overallRoot creates a gap Replacing with one of its children causes lots of gaps What node can we replace with overallRoot that wont cause any gaps? 4 5 8 7 10 13 9 11 Structure maintained, heap broken
- 12. Fixing Heap –percolate down Recursively swap parent with smallest child CSE 373 SP 18 - KASEY CHAMPION 12 4 5 8 7 10 13 9 11 4 13 5 13 13 11 percolateDown(node) { while (node.data is bigger than its children) { swap data with smaller child } }
- 13. Self Check –removeMin() on this tree CSE 373 SP 18 - KASEY CHAMPION 13 10 17 14 9 11 5 13 20 22 16 15 24 19 18 18 18 9 18 11
- 14. Implementing insert() Insert anode to ensure no gaps Fix heap invariant percolate UP CSE 373 SP 18 - KASEY CHAMPION 14 4 5 8 7 10 2 9 11 13 3 3 7 3 4
- 15. How long doespercolating take? Up and Down both go through all levels - O(h) How tall is the tree? - Complete trees are always balanced (all leaves in level h or h+1) - h = log n So, percolation is O(log n) CSE 373 SU 18 – BEN JONES 15
- 16. Finding the lastchild in a complete tree is O(n) Finding parents is difficult without back- links (O(n)), so percolate-up is hard CSE 373 SU 18 – BEN JONES 16 Problems A B C D E F G H I J
- 17. 0 1 23 4 5 6 7 8 9 10 11 CSE 373 SU 18 – BEN JONES 17 A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 Indices: min = last = insert location = left child of i = right child of i = parent of i = 0 n - 1 n 2i + 1 2i + 2 (i - 1) / 2
- 18. Runtimes Calculating Indices isϴ(1) peekMin = find min index = ϴ(1) removeMin = find min index + find last index + swap + percolate down = ϴ(1) + ϴ(1) + ϴ(1) + ϴ(log n) = ϴ(log n) insert = find insert location + add to array + percolate up = ϴ(1) + ϴ(1) + ϴ(log n) = ϴ(log n) CSE 373 SU 18 – BEN JONES 18
- 19. How Long tobuild a heap from scratch? n inserts at ϴ(log n) gives ϴ(n log n) But early inserts don’t need to percolate as far, is it actually better? 𝑖=0 log 𝑛 2𝑖 ⋅ ⅈ No. The basic strategy here was to always percolate up from the bottom. This means the largest layer needs to percolate the farthest. Can we do better? CSE 373 SU 18 – BEN JONES 19 = 𝜃 𝑛 log 𝑛
- 20. Floyd’s Build Heap MainIdea: Start from the bottom (end of array) and percolate down. This ensures that the largest layer has the least distance to percolate. We start with the structural invariants (complete binary tree) fulfilled, and then fix the ordering invariant (the heap property – parents smaller than children) After each percolation, the subtree rooted at the percolated node is a valid min-heap! buildHeap(array) – Modifies an array in-place to be a heap CSE 373 SU 18 – BEN JONES 20
- 21. Floyd’s buildHeap algorithm CSE373 SP 18 - KASEY CHAMPION 21 8 12 5 3 4 11 7 10 1 2 6 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 4 8 1 7 6 1. Add all values to back of array 2. percolateDown(parent) starting at last index Build a tree with the values: 12, 5, 11, 3, 10, 2, 9, 4, 8, 1, 7, 6 12 5 11 3 10 2 9
- 22. Floyd’s buildHeap algorithm CSE373 SP 18 - KASEY CHAMPION 22 8 12 5 3 4 11 7 10 1 2 6 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 4 8 1 7 6 1. Add all values to back of array 2. percolateDown(parent) starting at last index 1. percolateDown level 3 2. percolateDown level 2 3. percolateDown level 1 4. percolateDown level 0 Build a tree with the values: 12, 5, 11, 3, 10, 2, 9, 4, 8, 1, 7, 6 12 5 11 3 10 2 9 7 10 2 11 3 5 2 11
- 23. Floy’d buildHeap Runtime Forrepeated inserts we had 𝑖=0 log 𝑛 2𝑖 ⋅ ⅈ Work per node at the i-th level is now (log n – i) since we percolate down 𝑖=0 log 𝑛 2𝑖 ⋅ (log 𝑛 − ⅈ) = 𝜃 𝑛 CSE 373 SU 18 – BEN JONES 23
- 24. Heap Sort Can weuse a heap to sort data? Yes! Heap Sort: repeatedly removeMin, and add this to an output array. This takes an extra array of space. Can we do better? Yes! Re-use the space vacated at the end of the array after each remove. This reverses the sorting order – either reverse the list (O(n)), or use a max-heap! CSE 373 SU 18 – BEN JONES 24
- 25. In Place HeapSort CSE 373 SP 18 - KASEY CHAMPION 25 public void inPlaceHeapSort(collection) { E[] heap = buildHeap(collection) for (n) output[n – i - 1] = removeMin(heap) } Worst case runtime? Best case runtime? Average runtime? O(nlogn) O(nlogn) O(nlogn) 0 1 2 3 4 5 6 7 8 9 15 17 16 18 20 22 14 4 2 1 Heap Sorted Items Current Item Complication: final array is reversed! - Run reverse afterwards (O(n)) - Use a max heap - Reverse compare function to emulate max heap
- 26. Announcements Midterm is nextFriday in class - All material up to and including next Monday’s lecture is fair game HW3 (an individual written assignment) will be posted soon - Excellent midterm review (similar questions) - Due after midterm, but HIGHLY SUGGESTED you at least solve, if not write up, all of the questions before midterm as studying. Project 1 is due Friday by midnight CSE 373 SU 18 – BEN JONES 26