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)$

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)

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)

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)