Priority Queue
Last updated
Notes
Algorithmic Pattern
Last updated
Each item has a priority, and the dequeue method removes the item that has the highest priority. Basically, high-priority items are handled first.
When we implemented a priority queue with an array or a linked list, the efficiency of some operations is
ordered array
O(n)
O(1)
O(n)
O(1)
ordered list
O(n)
O(1)
O(1)
O(1)
unordered array
O(1)
O(n)
O(1)
O(n)
unordered list
O(1)
O(n)
O(1)
O(n)
Using a binary heap, the runtime of both the deleteMin and insert operations is
binary heap
O(log n)
O(log n)
O(log n)
O(1)