Sidetrack: Priority Queues
Some applications of queues require
- items processed in order of "priority"
- rather than in order of entry (FIFO — first in, first out)
Priority Queues (PQueues) provide this via:
-
join: insert item into PQueue with an associated priority (replacing enqueue)
-
leave: remove item with highest priority (replacing dequeue)
Time complexity for naive implementation of a PQueue containing N items …
- O(1) for
join O(N) for leave
Most efficient implementation ("heap") …
- O(log N) for
join, leave … more on this in week 4 (binary search trees)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}