In computer science, a priority queue is an abstract data type similar to a regular queue where each element has an associated priority determining 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 the Java standard library, the PriorityQueue class considers the lowest element with respect to their order as having the highest priority. 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.
Operations 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.
Implementation
Naive implementations 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.
insert elements into an unsorted array; find and extract element with highest priority Performance: "insert" performs in O ( 1 ) {\displaystyle O(1)} constant time, where "extract_max" performs in O ( n ) {\displaystyle O(n)} linear time. insert(element, priority): node.element ← element node.priority ← priority list.append(node)
extract_max(): highest ← 0 foreach node in list: if highest.priority < node.priority: highest ← node list.remove(highest) return highest.element
insert elements into a sorted array; extract first element Performance: "insert" performs in O ( n ) {\displaystyle O(n)} linear time, where "extract_max" performs in O ( 1 ) {\displaystyle O(1)} constant time. insert(element, priority): node.element ← element node.priority ← priority for i in [0...N]: element ← list.get_at_index(i) if element.priority < node.priority: list.insert_at_index(node, i + 1) return
extract_max(): highest ← list.get_at_index(0) list.remove(highest) return highest.element
Usual implementation To improve performance, priority queues are typically based on a heap, giving O ( log n ) {\displaystyle O(\log n)} performance for inserts and removals, and O ( n ) {\displaystyle O(n)} to build the heap initially from a set of n {\displaystyle n} elements. 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 ) {\displaystyle O(\log n)} time, although building trees from existing sequences of elements takes O ( n log n ) {\displaystyle O(n\log n)} time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries. From a space-complexity standpoint, using self-balancing binary search tree with linked list takes more storage, since it requires storing extra references to other nodes. From a computational-complexity standpoint, priority queues are congruent to sorting algorithms. The section on the equivalence of priority queues and sorting algorithms, below, describes how efficient sorting algorithms can create efficient priority queues.
Specialized heaps There are several specialized heap data structures that either supply additional operations or outperform heap-based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is { 1 , 2 , . . . , C } {\displaystyle \{1,2,...,C\}} .
… excerpt ends here. Continue reading the full article.
