Unformatted text preview:

1. A priority queue has the same operations as a regular queue, except the items are NOT returned in the FIFO (first-in, first-out) order. Instead, each item has a proirity that determines the order they are removed.A hospital emergence room operates like a priority queue -- the person with the most serious injure hashighest priority even if they just arrived. a) Suppose that we have a priority queue with integer priorities such that the smallest integer corresponds tothe highest priority. For the following priority queue, which item would be dequeued next?40301057913priority queue:b) To implement a priority queue, we could use an unorder Python list. If we did, what would be theworst-case theta (Θ( )) notation for each of the following methods: (justify your answer) enqueue: dequeue:c) To implement a priority queue, we could use a linked list ordered by priorities, e.g., theLinkedPriorityQueue class of chapter 15. If we did, what would be the worst-case theta (Θ( )) notation foreach of the following methods: (justify your answer) enqueue: dequeue2. Sections 18.9 - 18.11 discuss a very “non-intuitive”, but powerful list/array-based approach to implementa priority queue, call a heap. The list/array is used to store a complete binary tree (a full tree with anyadditional leaves as far left as possible) with the items being arranges by heap-order property, i.e., each nodeis less than either of its children. An example of a min heap “viewed” an a complete binary tree would be: 615 1011420 5020300125 117[0][1][2][3] [4][5][6][7] [8][9]Data Structures Lecture 10 Name:_______________Lecture 10 Page 1a) For the above heap, the list/array indexes are indicated in [ ]'s. For a node at index i, what is the index of: its left child if it exists: its right child if it exists: its parent if it exists:b) What would the above heap look like after adding 13 and then 8?c) What is the worst-case theta (Θ( )) notation for adding a new item in the heap?d) What is the worst-case theta (Θ( )) notation for removing the smallest item from the heap?Data Structures Lecture 10 Name:_______________Lecture 10 Page


View Full Document

UNI CS 1520 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?