CS234 Lecture Notes - Lecture 11: Priority Queue, Linked List, Binary Tree
Document Summary
Fifo - protocol - first in first out enquenues. Some applications require the use of a queue in which items are assigned a priority p 0. Items with equal priority are dequeued using the fifo order dequeues back front. Unbounded - unlimited range of priorities no bounds on p. Priorityqueue() - creates an empty priority q unbounded. Bpriorityqueue(maxlevels) - creates an empty priority q, p < maxlevels. Enqueue(item, priority) - adds item to priority q. Dequeue() - returns and removes the highest priority item. L = [10, 12, 4, 1, 9, 13] def: Enqueue - add to the back o(n) is the worst case. Dequeue - find max priority and remove first item with that priority o(n) Enqueue - add item into its sorted position. Dequeue - remove from the front of the queue o(1) front. Linked list (singly - linked list) back back. Can we improve on o(n) time for dequeueing/enqueueing items.