queue

README

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.

See also

Priority Queue on Wikipedia

Written for Swift Algorithm Club by Matthijs Hollemans

Documentation

Index

• type PriorityQueue
  • func PriorityQueueInit[T comparable](sort func(T, T) bool) *PriorityQueue[T]
  • func (self *PriorityQueue[T]) ChangePriority(index int, value T)
  • func (self *PriorityQueue[T]) Count() int
  • func (self *PriorityQueue[T]) Dequeue() (T, bool)
  • func (self *PriorityQueue[T]) Enqueue(element T)
  • func (self *PriorityQueue[T]) IndexOf(element T) int
  • func (self *PriorityQueue[T]) IsEmpty() bool
  • func (self *PriorityQueue[T]) Peek() (T, bool)

Types

type PriorityQueue

type PriorityQueue[T comparable] struct {
	// contains filtered or unexported fields
}

Priority Queue, a queue where the most "important" items are at the front of the queue.

The heap is a natural data structure for a priority queue, so this object simply wraps the Heap struct.

All operations are O(lg n).

Just like a heap can be a max-heap or min-heap, the queue can be a max-priority queue (largest element first) or a min-priority queue (smallest element first).

func PriorityQueueInit

func PriorityQueueInit[T comparable](sort func(T, T) bool) *PriorityQueue[T]

To create a max-priority queue, supply a GreaterThan sort function. For a min-priority queue, use the LessThan sort function.

func (*PriorityQueue[T]) ChangePriority

func (self *PriorityQueue[T]) ChangePriority(index int, value T)

Allows you to change the priority of an element. In a max-priority queue, the new priority should be larger than the old one; in a min-priority queue it should be smaller.

func (*PriorityQueue[T]) Count

func (self *PriorityQueue[T]) Count() int

func (*PriorityQueue[T]) Dequeue

func (self *PriorityQueue[T]) Dequeue() (T, bool)

func (*PriorityQueue[T]) Enqueue

func (self *PriorityQueue[T]) Enqueue(element T)

func (*PriorityQueue[T]) IndexOf

func (self *PriorityQueue[T]) IndexOf(element T) int

func (*PriorityQueue[T]) IsEmpty

func (self *PriorityQueue[T]) IsEmpty() bool

func (*PriorityQueue[T]) Peek

func (self *PriorityQueue[T]) Peek() (T, bool)