Priority Queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

  • stack — elements are pulled in last-in first-out-order (e.g. a stack of papers)
  • queue — elements are pulled in first-in first-out-order (e.g. a line in a cafeteria)

It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

A priority queue must at least support the following operations:

  • insert_with_priority: add an element to the queue with an associated priority
  • pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it (also known as "pop_element(Off)", "get_maximum_element", or "get_front(most)_element"; some conventions consider lower priorities to be higher, so this may also be known as "get_minimum_element", and is often referred to as "get-min" in the literature; the literature also sometimes implement separate "peek_at_highest_priority_element" and "delete_element" functions, which can be combined to produce "pull_highest_priority_element")

More advanced implementations may support more complicated operations, such as pull_lowest_priority_element, inspecting the first few highest- or lowest-priority elements (peeking at the highest priority element can be made O(1) time in nearly all implementations), clearing the queue, clearing subsets of the queue, performing a batch insert, merging two or more queues into one, incrementing priority of any element, etc.

Read more about Priority Queue:  Similarity To Queues, Libraries

Other articles related to "priority queue, queue, priority, priority queues":

Cartesian Tree - Application in Sorting
... as a version of selection sort or heap sort that maintains a priority queue of candidate minima, and that at each step finds and removes the minimum value in this queue, moving this value to the end of an ... In their algorithm, the priority queue consists only of elements whose parent in the Cartesian tree has already been found and removed ... tree for the input sequence Initialize a priority queue, initially containing only the tree root While the priority queue is non-empty Find and remove the minimum value x in the ...
Priority Queue - Applications - ROAM Triangulation Algorithm
... The algorithm assigns each triangle in the terrain a priority, usually related to the error decrease if that triangle would be split ... The algorithm uses two priority queues, one for triangles that can be split and another for triangles that can be merged ... In each step the triangle from the split queue with the highest priority is split, or the triangle from the merge queue with the lowest priority is merged with its neighbours ...
Watershed (image Processing) - Algorithms - Meyer's Flooding Algorithm
... The neighboring pixels of each marked area are inserted into a priority queue with a priority level corresponding to the gray level of the pixel ... The pixel with the highest priority level is extracted from the priority queue ... All non-marked neighbors that are not yet in the priority queue are put into the priority queue ...
Huffman Coding - Basic Technique - Compression
... The simplest construction algorithm uses a priority queue where the node with lowest probability is given highest priority Create a leaf node for each symbol and add it to the ... While there is more than one node in the queue Remove the two nodes of highest priority (lowest probability) from the queue Create a new internal node with these two nodes as ... Add the new node to the queue ...
Bentley–Ottmann Algorithm - Data Structures
... A priority queue (the "event queue"), used to maintain a sequence of potential future events in the Bentley–Ottmann algorithm ... Similarly, the priority queue may be a binary heap or any other logarithmic-time priority queue more sophisticated priority queues such as a Fibonacci heap are not necessary ...

Famous quotes containing the words queue and/or priority:

    English people apparently queue up as a sort of hobby. A family man might pass a mild autumn evening by taking the wife and kids to stand in the cinema queue for a while and then leading them over for a few minutes in the sweetshop queue and then, as a special treat for the kids, saying “Perhaps we’ve time to have a look at the Number Thirty-One bus queue before we turn in.”
    Calvin Trillin (b. 1940)

    It can be fairly argued that the highest priority for mankind is to save itself from extinction. However, it can also be argued that a society that neglects its children and robs them of their human potential can extinguish itself without an external enemy.
    Selma Fraiberg (20th century)