In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like “a list” or “a map”; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
A priority queue must at least support the following operations:
- insert_with_priority: add an element to the queue with an associated priority.
- pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.
To improve performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals, and O(n log n) to build initially.
Variants of the basic heap data structure such as pairing heaps or Fibonacci heaps can provide better bounds for some operations. Alternatively, when a self-balancing binary search tree is used, insertion and removal also take O(log n) time, although building trees from existing sequences of elements takes O(n log n) time.