notes11a.pdf

June 11, 2013 Last Class  We covered: o Stacks – LIFO o Queues – FIFO Queue  Linear collection of items  FIFO protocol: First In First Out o Items are removed from the queue (i.e. dequeue) from the front, and items are entered into the queue (i.e. enqueue) from the back Priority Queue  Some applications require the use of a queue in which items are assigned a priority, p >= 0 o Higher priority items are dequeued first o Items with equal priority still follow the FIFO protocol, and are dequeued in the order they were entered Example: Printer queue Back of Queue pdf | 9 txt | 3 jpg | 3 docx | 5 Front of Queue  Calling dequeue will search the queue for the highest priority and remove the first instance of that item. In this example, dequeue will remove the pdf with priority 9 Two Types (of Priority Queues): 1. Bounded – limited range of priorities a. 0 <= p <= m, such that m > 0 2. Unbounded – unlimited range of priorities a. No bounds on p ADT Priority Queue  Data: linear collection of items  Operations: o PriorityQueue() – create an empty, unbounded priority queue o BPriorityQueue(maxLevels) – create an empty priority queue where items have priorities less than maxLevels o isEmpty() – returns True if the queue is empty and False otherwise o length() – returns the number of items in queue o enqueue(item, priority) – add item to queue o dequeue() – returns and removes the highest priority item June 11, 2013 Using the Priority Queue Python code L = [10, 12, 4, 1, 9, 13] PQ = PriorityQueue() for x in L: PQ.enqueue(x, x) pos = 0 while not PQ.isEmpty(): L[pos] = PQ.dequeue() pos += 1 Analysis of the above code PQ at the end of the “for” loop: Back of Queue 13 | 13 9 | 9 1 | 1 4 | 4 12 | 12 10 | 10 Front of Queue L after the “while” loop: L = [13, 12, 10, 9, 4, 1] Priority Queue Implementation Unbounded Priority Queue Two approaches:  Python List  Linked Lists Python List 1. Store items in FIFO order Ex. 12, 5, 7, 13 Back of PQ | 13 | 7 | 5 | 12 Front of PQ Operations: a. Enqueue – add to back of PQ (the front of the Python list) O(n) b. Dequeue – find the max priority and remove the first item with that priority O(n) 2. Store in increasing sorted order Ex. 12, 5, 7, 13 Back of PQ | 5 | 7 | 12 | 13 Front of PQ Operations: a. Enqueue – adds the item to its sorted position O(n) b. Dequeue – remove from the front of the queue O(1) June 11, 2013 Linked List 1. FIFO Order Back of PQ | 13 | | 7 | | 5 | | 12 | Front of PQ a. Enqueue O(1)