Priority Queue
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
insert
deleteMin
remove
findMin
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
insert
deleteMin
remove
findMin
binary heap
O(log n)
O(log n)
O(log n)
O(1)
Last updated