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