Editing Priority queue (section)

{{short description|Abstract data type in computer science}}

In [[computer science]], a '''priority queue''' is an [[abstract data type]] similar to a regular [[queue (abstract data type)|queue]] or [[stack (abstract data type)|stack]] abstract data type.

In a priority queue, each element has an associated ''priority'', which determines its order of service.<ref name=":0">{{Cite journal |last=Miller Jr. |first=Robert G. |date=1960 |title=Priority queues |url=https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-31/issue-1/Priority-Queues/10.1214/aoms/1177705990.pdf |journal=The Annals of Mathematical Statistics |volume=31 |pages=86–103 |publisher=Stanford University|doi=10.1214/aoms/1177705990 }}</ref> Priority queue serves highest priority items first.<ref name=":0" /> 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 (programming language)|Java]] standard library, ''PriorityQueue'''s the least elements with respect to the order have the highest priority.<ref>{{Cite web |title=PriorityQueue (Java SE 9 & JDK 9 ) |url=https://docs.oracle.com/javase/9/docs/api/java/util/PriorityQueue.html |access-date=2025-03-13 |website=docs.oracle.com}}</ref> This implementation detail is without much practical significance, since passing to the [[converse relation|opposite order relation]] turns the least values into the greatest, and vice versa.

While priority queues are often implemented using [[Heap (data structure) |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 data structure|array]].