Priority Queue
- A generalization of Queues
- All elements inserted have some priority
- Elements with the highest or lowest priority are removed first
- Implemented using Binary Heap
Operations
- Insertion
- Peek
- ExtractMin or ExtractMax
Implementations
| Structure | Insert | Extract | Peek |
|---|---|---|---|
| Unsorted Array/List | O(1) | O(n) | O(n) |
| Sorted Array/List | O(n) | O(1) | O(1) |
| Balanced trees | O(log n) | O(log n) | O(log n) |
| Binary Heap | O(log n) | O(log n) | O(1) |