CS234 Lecture Notes - Lecture 11: Priority Queue, Linked List, Binary Tree

35 views4 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents