Priority queue

• 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.


        This is also known as "pop_element(Off)", "get_maximum_element", or "get_front(most)_element".
        Some conventions reverse the order of priorities, considering lower values to be higher priority, so this may also be known as "get_minimum_element", and is often referred to as "get-min" in the literature.
        This may instead be specified as separate "peek_at_highest_priority_element" and "delete_element" functions, which can be combined to produce "pull_highest_priority_element".

In addition, peek (in this context often called find-max or find-min), which returns the highest priority element but does not modify the queue, is very frequently implemented, and nearly always executes in O(1) time. This operation and its O(1) performance is crucial to many applications of priority queues.


Using a priority queue to sort
he semantics of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several sorting algorithms, once the layer of abstraction provided by the priority queue is removed


    Heapsort if the priority queue is implemented with a heap.
    Smoothsort if the priority queue is implemented with a Leonardo heap.
    Selection sort if the priority queue is implemented with an unordered array.
    Insertion sort if the priority queue is implemented with an ordered array.
    Tree sort if the priority queue is implemented with a self-balancing binary search tree.


Applications

Bandwidth management
Priority queuing can be used to manage limited resources such as bandwidth on a transmission line from a network router.


Dijkstra's algorithm
When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra's algorithm, although one also needs the ability to alter the priority of a particular vertex in the priority queue efficiently.


Huffman coding
Huffman coding requires one to repeatedly obtain the two lowest-frequency trees. A priority queue makes this efficient.

http://en.wikipedia.org/wiki/Priority_queue