# Priority queue

 related topics {math, number, function} {system, computer, user} {rate, high, increase}

A priority queue is an abstract data type in computer programming that supports the following three operations:

• `insertWithPriority`: add an element to the queue with an associated priority
• `getNext`: remove the element from the queue that has the highest priority, and return it (also known as "PopElement(Off)", or "GetMinimum")
• `peekAtNext` (optional): look at the element with highest priority without removing it.

For an analogy, see the Implementation section below.

## Contents

### Similarity to queues

One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority one is retrieved first.

Stacks and queues may be modeled as particular kinds of priority queues. 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.

### Simple implementations

There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is:

• Sorted list implementation: Like a checkout line at the supermarket, but where important people get to "cut" in front of less important people. (O(n) insertion time, O(1) get-next time, O(n*log(n)) to build)
• Unsorted list implementation: Keep a list of elements as the queue. To add an element, append it to the end. To get the next element, search through all elements for the one with the highest priority. (O(1) insertion time, O(n) get-next due to search)