Priority queue

In computer science, a priority queue is an abstract data type similar to a regular queue or stack abstract data type.

In a priority queue, each element has an associated priority, which determines its order of service. Priority queue serves highest priority items first. Priority values have to be instances of an ordered data type, and higher priority can be given either to the lesser or to the greater values with respect to the given order relation. For example, in Java standard library, PriorityQueue's the least elements with respect to the order have the highest priority. This implementation detail is without much practical significance, since passing to the opposite order relation turns the least values into the greatest, and vice versa.

While priority queues are often implemented using heaps, they are conceptually distinct. A priority queue can be implemented with a heap or with other methods; just as a list can be implemented with a linked list or with an array.

A priority queue has the following operations:

Stacks and queues can be implemented as particular kinds of priority queues, with the priority determined by the order in which the elements are inserted. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.

In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.

One can create a simple, but inefficient priority queue in a number of ways. These naive implementations can demonstrate the expected behaviour of a priority queue in a simpler manner.

To improve performance, priority queues are typically based on a heap, giving ${\displaystyle O(\log n)}$ performance for inserts and removals, and ${\displaystyle O(n)}$ to build the heap initially from a set of ${\displaystyle n}$ elements. Variants of the basic heap data structure such as pairing heaps or Fibonacci heaps can provide better bounds for some operations.