Priority queues
A priority queue is an abstract data type operating similarly to a queue , except that elements are inserted with an associated priority. When elements are removed (dequeued), they are served in the order of their priority, rather than in order of insertion.
Common operations
| Name | Description |
|---|---|
size() |
gets the number of elements stored in the queue |
peek() |
gets the highest-priority element of the queue |
dequeue() |
removes and returns the highest-priority item from the queue |
enqueue(p, e) |
inserts element e into the queue with priority p |
Binary heap implementation
Priority queues are commonly implemented via heaps , which allow access the the highest priority item in $\mathcal{O}(1)$-time, and insertion and deletion from the queue in $\mathcal{O}(\log n)$-time.