Priority Queue

A priority queue is a queue where the most important element is always at the front.

The queue can be a max-priority queue (largest element first) or a min-priority queue (smallest element first).

Why use a priority queue?

Priority queues are useful for algorithms that need to process a (large) number of items and where you repeatedly need to identify which one is now the biggest or smallest -- or however you define "most important".

Examples of algorithms that can benefit from a priority queue:

Event-driven simulations. Each event is given a timestamp and you want events to be performed in order of their timestamps. The priority queue makes it easy to find the next event that needs to be simulated.
Dijkstra's algorithm for graph searching uses a priority queue to calculate the minimum cost.
Huffman coding for data compression. This algorithm builds up a compression tree. It repeatedly needs to find the two nodes with the smallest frequencies that do not have a parent node yet.
A* pathfinding for artificial intelligence.
Lots of other places!

With a regular queue or plain old array you'd need to scan the entire sequence over and over to find the next largest item. A priority queue is optimized for this sort of thing.

What can you do with a priority queue?

Common operations on a priority queue:

Enqueue: inserts a new element into the queue.
Dequeue: removes and returns the queue's most important element.
Find Minimum or Find Maximum: returns the most important element but does not remove it.
Change Priority: for when your algorithm decides that an element has become more important while it's already in the queue.

How to implement a priority queue

There are different ways to implement priority queues:

As a sorted array. The most important item is at the end of the array. Downside: inserting new items is slow because they must be inserted in sorted order.
As a balanced binary search tree. This is great for making a double-ended priority queue because it implements both "find minimum" and "find maximum" efficiently.
As a heap. The heap is a natural data structure for a priority queue. In fact, the two terms are often used as synonyms. A heap is more efficient than a sorted array because a heap only has to be partially sorted. All heap operations are O(log n).

Here's a Swift priority queue based on a heap:

public struct PriorityQueue<T> {
  fileprivate var heap: Heap<T>

  public init(sort: (T, T) -> Bool) {
    heap = Heap(sort: sort)
  }

  public var isEmpty: Bool {
    return heap.isEmpty
  }

  public var count: Int {
    return heap.count
  }

  public func peek() -> T? {
    return heap.peek()
  }

  public mutating func enqueue(element: T) {
    heap.insert(element)
  }

  public mutating func dequeue() -> T? {
    return heap.remove()
  }

  public mutating func changePriority(index i: Int, value: T) {
    return heap.replace(index: i, value: value)
  }
}

As you can see, there's nothing much to it. Making a priority queue is easy if you have a heap because a heap is pretty much a priority queue.

Priority Queue

Why use a priority queue?

What can you do with a priority queue?

How to implement a priority queue

See also