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