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.^[1] Priority queue serves highest priority items first.^[1] 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.^[2] 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.