Priority Queues and Implementations in CSE 332 SU 18
Explore priority queues in data structures and parallelism with CSE 332 SU 18 professor Robbie Weber. Learn about the logistics of the course projects, a new ADT for priority queues, Priority Queue ADT uses, and implementing priority queues using various data structures.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Priority Queues Data Structures and Parallelism CSE 332 SU 18 - ROBBIE WEBER 1
Logistics Project 1: -Due Thursday July 5th at 11:30 PM -One Checkpoint in lecture on Friday Checkpoint: -The project spec lists where we recommend you be (it represents being about halfway). -At the end of lecture on Friday, you ll talk to a staff member about where you are on the project. -As long as you ve made a good faith effort to be half As long as you ve made a good faith effort to be half- -way done, you ll pass the checkpoint. checkpoint. Tokens: -4 tokens per person. You can use them to either -Get a late day on a project (max 2 per project) -Redo an exercise in the last week of the quarter. way done, you ll pass the CSE 332 SU 18 - ROBBIE WEBER 2
More Logistics! Exercise 01 will come out tonight, due Friday (it should make sense after class today) Robbie is out of town most of next week. -Ben Jones (another instructor) will cover lectures on Wednesday and Friday. -I ll be checking email at least once per day. CSE 332 SU 18 - ROBBIE WEBER 3
A New ADT Our previous worklists (stacks, queues, etc.) all choose the next element based on the order they were inserted. That s not always a good idea. Emergency rooms aren t first-come-first-served. Sometimes our objects come with a priority priority, that tells us what we need to do next. An ADT that can handle a line with priorities is a priority queue. priority queue. CSE 332 SU 18 - ROBBIE WEBER 4
Priority Queue ADT Uses: Operating System Well-designed printers Huffman Codes (in 143) Sorting (in Project 2) Graph algorithms Min Priority Queue ADT state state Set of comparable values - Ordered based on priority behavior behavior insert(value) insert(value) add a new element to the collection removeMin removeMin() () returns the element with the smallest priority, removes it from the collection peekMin peekMin() () find, but do not remove the element with the smallest priority CSE 332 SU 18 - ROBBIE WEBER 5
Implementing Priority Queues: Take I Maybe we already know how to implement a priority queue. How long would insert and removeMin take with these data structures? Insert Insert removeMin removeMin Unsorted Array Unsorted Linked List Sorted Linked List Sorted Circular Array Binary Search Tree For Array implementations, assume that the array is not yet full. Other than this assumption, do worst case worst case analysis. CSE 332 SU 18 - ROBBIE WEBER 6
Review: Binary Search Trees A BST is: 1. A binary tree 2. For each node, everything in its left subtree is smaller than it and everything in its right subtree is larger than it. CSE 332 SU 18 - ROBBIE WEBER 7
Are These BSTs? 6 6 1 5 8 4 8 2 3 7 9 3 2 5 4 5 CSE 332 SU 18 - ROBBIE WEBER 8
Implementing Priority Queues: Take I Maybe we already know how to implement a priority queue. How long would insert and removeMin take with these data structures? Insert Insert removeMin removeMin Unsorted Array (1) (?) Unsorted Linked List (1) (?) Sorted Linked List (?) (1) Sorted Circular Array (?) (1) Binary Search Tree For Array implementations, assume that the array is not yet full. Other than this assumption, do worst case worst case analysis. CSE 332 SU 18 - ROBBIE WEBER 9
Implementing Priority Queues: Take I Maybe we already know how to implement a priority queue. How long would insert and removeMin take with these data structures? Insert Insert removeMin removeMin Unsorted Array (1) (?) Unsorted Linked List (1) (?) Sorted Linked List (?) (1) Sorted Circular Array (?) (1) Binary Search Tree (?) (?) For Array implementations, assume that the array is not yet full. Other than this assumption, do worst case worst case analysis. CSE 332 SU 18 - ROBBIE WEBER 10
Implementing Priority Queues: Take II BSTs have really bad behavior in the worst worst case, but is it actually a common problem? Fact: On average, the height of a BST is ?(log?) (for some suitable definition of average ) Can we somehow get that behavior in the worst case worst case for priority queues? CSE 332 SU 18 - ROBBIE WEBER 11
BST Properties A BST is: 1. A binary tree 2. For each node, everything in its left subtree is smaller than it and everything in its right subtree is larger than it. Point 2 is what causes the really bad behavior in the worst case. We probably don t want exactly that requirement for implementing a priority queue. Maybe we can explicitly enforce that we don t get a degenerate tree. CSE 332 SU 18 - ROBBIE WEBER 12
Binary Heaps A Binary Heap is 1. A Binary Tree 2. Every node is less than or equal to all of its children -In particular, the smallest element must be the root! 3. The tree is complete complete -Every level of the tree is completely filled, except possibly the last row, which is filled from left to right. -No degenerate trees! CSE 332 SU 18 - ROBBIE WEBER 13
Tree Words Height the number of edges on the longest path from the root to a leaf. 1 2 4 Height 1 Height 4 2 6 4 5 3 4 5 CSE 332 SU 18 - ROBBIE WEBER 14
Tree Words Complete every row is completely filled, except possibly the last row, which is filled from left to right. Perfect every row is completely filled 2 4 2 4 2 4 6 4 5 6 4 5 6 4 5 5 5 5 8 8 8 9 9 2 Complete, but not perfect Neither Both Perfect and Complete CSE 332 SU 18 - ROBBIE WEBER 15
Heights of Perfect Trees How many nodes are there in level ? of a perfect binary tree? On the whiteboard we derived that the number of nodes on level ? of a binary tree was 2?. Thus the total number of nodes in a perfect binary tree of height is 2?= 2 +1 1. So if we have ? nodes in a perfect tree, we can use the formula ? = 2 +1 1 to conclude that = ?(log?),so A perfect tree with ? nodes has height ?(log?). A similar argument can show the same statement for complete trees. ?=0 CSE 332 SU 18 - ROBBIE WEBER 16
Binary Heaps A Binary Heap is 1. A Binary Tree 2. Every node is less than or equal to all of its children -In particular, the smallest element must be the root! 3. The tree is complete complete -Every level of the tree is completely filled, except possibly the last row, which is filled from left to right. -No degenerate trees! CSE 332 SU 18 - ROBBIE WEBER 17
Implementing Heaps Let s start with removeMin. 2 4 6 4 5 5 8 9 Idea: take the bottom right-most node and use it to plug the hole Shape is correct now But that value might be to big. We need to percolate it down CSE 332 SU 18 - ROBBIE WEBER 18
Implementing Heaps Insertion 3 1 4 7 1 3 1 7 5 8 6 What is the shape going to be after the insertion? Again, plug the hole first. Might violate the heap property. Percolate it up CSE 332 SU 18 - ROBBIE WEBER 19
An Optimization Pointers are annoying. They re also slow. Our tree is so nicely shaped, we don t need pointers We can use an array instead. 1 4 3 7 5 8 6 4 3 5 8 7 1 6 0 1 2 3 4 5 6 7 8 9 10 CSE 332 SU 18 - ROBBIE WEBER 20
An Optimization If I m at index ?, what is the index of: My left child, right child and parent? My left child: 2? My right child: 2? + 1 1 4 3 7 5 8 6 ? 2 My parent: 4 3 5 8 7 1 6 0 1 2 3 4 5 6 7 8 9 10 CSE 332 SU 18 - ROBBIE WEBER 21
