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] The order of service is largely based on implementation. Traditionally, scholars describe priority queue as serving highest priority first.^[1] However, in modern software it is merely an implementation detail. For example, in Java standard library, PriorityQueue serves lowest priority first by default.^[2]

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.