Applications

Sorting

An obvious application for priority queues is the sorting problem: To sort $n$ numbers, we simply

  1. use $n$ inserts to put all the elements into the priority queue
  2. take them out in sorted order by calling extract-min $n$ times.

Now different implementations of the priority queue will give different sorting algorithms. For example, the well known selection sort and insertion sort algorithms implicitly use the unsorted and sorted array priority queue implementation, respectively. In these naive solutions, either inserting or extracting the minimum is slow and thus the whole sorting algorithms are slow. However, if we instead use a binary heap, we get the so called heapsort algorithm, which is much faster.

sorting algorithm priority queue implementation insert extract-min total for \(n\) inserts and \(n\) extract-mins
selection sort unsorted array \(O(1)\) \(O(n)\) \(O(n^2)\)
insertion sort sorted array \(O(n)\) \(O(1)\) \(O(n^2)\)
heapsort heap \(O(\log n)\) \(O(\log n)\) \(O(n\log n)\)

Interestingly, it can be proved that no sorting algorithm can be better than $O(n\log n)$ time (in the comparison model), so the heapsort algorithm is in some sense optimal (it is $O(n\log n)$ time in worst case and requires only $O(1)$ space in addition to the array being sorted). One might object that in practice, quicksort is much faster that heapsort, but the $O(n\log n)$ time for quicksort is only in average case. In fact, the introsort algorithm which is implemented in the widely used STL library in C++ is a combination of quicksort and heapsort (the rough idea is to start with quicksort, but switch to heapsort when it performs badly).

Remark: Any priority queue gives us a sorting algorithm. Interestingly, as shown by Thorup, the converse is also true and any sorting algorithm can be used to develop a priority queue.

Shortest path

Given a map with cities and roads between them (with known lengths and speed limits), we would like to find the shortest or the fastest route between two cities. More abstractly, let $G$ be a weighted graph with $n$ vertices and $m$ edges, and denote $\ell(u,v)$ the length of edge $(u,v)$. The problem is to find the shortest path between given vertices $s$ and $t$.

Assume that all the lengths are non-negative. Then the problem can be solved by Dijkstra’s algorithm, which works roughly as follows:

For each vertex $v$, keep its tentative distance $d(v)$ from $s$. In the beginning, $d(s) = 0$ and $d(v) = \infty$ for all other vertices. Also keep a set $S$ of vertices, for which the tentative distance is not yet final (in the beginning, its all vertices).

While $S$ is not empty,

  1. let $u\in S$ such that $d(u)$ is minimum; declare $d(u)$ final and remove it from $S$;
  2. for all neighbours $v$ of $u$, set $d(v) = \min \{ d(v), d(u) + \ell(u,v) \}$.

The set $S$ is actually a priority queue, where the elements – vertices are ordered by their distance $d(v)$ from the start; What is the time complexity of the algorithm? In the first step we insert all vertices to $S$ (i.e., $n$ times insert); then in step 2.1, we remove the minimum element, this happens also $n$ times.

The time complexity of the algorithm is

$n\times [T($insert$) + T($extract-min$)] + m\times T($decrease-key$)$

which is

priority queue implementation complexity
array \(O(n^2)\)
heap \(O(m\log n)\)
d-ary heap with \(d=2+m/n\) \(O(m\log_{m/n} n)\)
Fibonacci heap \(O(m + n\log n)\)

Note that for dense graphs where the number of edges $m=\Theta(n^2)$, the simple array implementation is optimal and the binary heap implementation is slightly slower. On the other hand, most of the real-world graphs are sparse. For instance, if the graph is a rectangular grid, \(m\approx 2n\); if the graph is planar (can be drawn in a plane without edge crossings), the number of edges is linear \((m\leq 3n - 6)\).

The \(d\)-ary heap implementation is optimal when \(m=\Omega(n^{1+\varepsilon})\) – for such \(m\), \(O(m\log_{m/n} n)=O(m)\). Dijkstra’s algorithm with Fibonacci heap is optimal when \(m=\Omega(n\log n)\).

Minimum spanning tree

Imagine that we would like to build an electrical power network: we need to interconnect all the given cities but we would like to minimize the total wire length. This problem was actually the original motivation to study the minimum spanning tree (MST) problem. Given a weighted graph $G$, a spanning tree is a subgraph that is a tree (connected, without cycles) and connects all vertices. Its weight is the total weight of its edges. In the MST problem we would like to find a spanning tree with minimum weight.

One way to find it is using the Jarník-Prim algorithm which is very similar to the Dijkstra’s algorithm in the previous section. The time complexity analysis is exactly the same; in particular, we can improve the algorithm by using a better priority queue implementation.