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.