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 $\text{O}(n)$

	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 $\text{O}(\log n)$

	insert	deleteMin	remove	findMin
binary heap	O(log n)	O(log n)	O(log n)	O(1)