Function Repository Resource:

PriorityQueue

Source Notebook

Provide a priority queue data structure with its standard operations

Contributed by: Daniel Lichtblau

ResourceFunction["PriorityQueue"][]

returns a priority queue initialized with default settings.

ResourceFunction["PriorityQueue"][{"InitialSize"→size,"NullElement"→null,"ComparisonFunction"→comp},"Initialize"]

returns a priority queue initialized to have length size, null element null and comparison function comp.

ResourceFunction["PriorityQueue"][inits,vals,"Initialize"]

returns a priority queue initialized with parameters in inits and containing values vals.

ResourceFunction["PriorityQueue"][queue,value,"Enqueue"]

places value in queue.

ResourceFunction["PriorityQueue"][queue,operation]

performs the specified operation on queue.

Details

Priority queues can be used for sorting by a given ordering function.

Priority queues are also used in the implementation of Prim's algorithm for computing minimum spanning trees.

The default values for "InitialSize", "NullElement" and "ComparisonFunction" are 16, Missing["empty slot"] and Greater, respectively.

"Initialize" can be omitted whenever the first argument is a list of three initialization settings.

In ResourceFunction["PriorityQueue"][queue,value,"Enqueue"], the explicit "Enqueue" can be omitted.

In ResourceFunction["PriorityQueue"][queue,operation], the allowed values of operation are "Length", "EmptyQ", "Dequeue" and "Peek", which perform the following actions:

"Length"

gives the number of elements currently in the queue

"EmptyQ"

gives True if the queue contains no elements, and gives False otherwise

"Dequeue"

removes the largest element from the queue and returns its value

"Peek"

gives the largest value without removing it from the queue

In ResourceFunction["PriorityQueue"][queue], the operation "Dequeue" is assumed. In typical usage, one would remove and store the largest element by doing topval=ResourceFunction["PriorityQueue"][queue,"Dequeue"]. Dequeuing all elements from a heap results in a list sorted according to the specified ordering function.

This implementation of priority queues uses binary heaps; this is a common technique.

In binary heap implementations such as this one, each element in a priority queue has either zero, one or two children. If the j^thelement has children, they will be located at positions 2j and 2j+1 (with the latter position empty if there is ony one child). Elements are contiguous in the sense that there is never a hole (empty slot) until after the last element.

Each child is ordered less than its parent, but the children do not satisfy a prescribed order with respect to one another.

A priority queue is similar to a binary tree with breadth-first ordering (children considered lower than parents), except children are not always placed in their relative ordering.

Generally, a priority queue is an array of fixed size, so adding and removing elements do not incur memory allocation or deallocation.

The one exception is when adding an element to a queue that is at capacity, at which point the heap size is doubled.

ResourceFunction["PriorityQueue"] has the attribute HoldFirst.

Examples

Basic Examples (9)

Initialize a priority queue (aka ordered heap) with 20 random reals between -1 and 1:

In[1]:=

SeedRandom[1234];
heap = ResourceFunction[
"PriorityQueue"][{"InitialSize" -> 16, "NullElement" -> Missing[], "ComparisonFunction" -> Greater}, inits = RandomReal[{-1, 1}, 20]];

Check the size:

In[2]:=

Out[2]=

Check the value of the largest element:

In[3]:=

Out[3]=

Add 80 more random values to the heap:

In[4]:=

Recheck the length and largest value:

In[5]:=

Out[5]=

When we dequeue elements one-by-one, the result is a sorted list of values; this method is called the "heap-sort" algorithm:

In[6]:=

sorted = Reap[
While [! ResourceFunction["PriorityQueue"][heap, "EmptyQ"], Sow[ResourceFunction["PriorityQueue"][heap, "Dequeue"]]]][[2, 1]]

Out[6]=

Check that it is indeed empty:

In[7]:=

Out[7]=

An alternative check is that the length is zero:

In[8]:=

Out[8]=

Check that the result is correctly sorted largest-to-smallest:

In[9]:=

Out[9]=

Scope (2)

PriorityQueue can work with any data type for which an ordering exists, such as words with alphabetical order:

In[10]:=

SeedRandom[1234];
size = 40;
words = RandomWord[size];
heap = ResourceFunction[
"PriorityQueue"][{"InitialSize" -> size, "NullElement" -> Missing[], "ComparisonFunction" -> (AlphabeticOrder[##] === 1 &)}, words];

Now sort them in dictionary order by dequeuing:

In[11]:=

sortedwords = Reap[While [! ResourceFunction["PriorityQueue"][heap, "EmptyQ"], Sow[ResourceFunction["PriorityQueue"][heap, "Dequeue"]]]][[2, 1]]

Out[11]=

Properties and Relations (5)

For a queue of size n, we expect speed proportional to nlog(n) for creating and removing all elements. We test this by timing a basic sorting, then doubling the size twice.

Use a queue to enqueue 10,000 random values:

In[12]:=

$defaultNames = {"InitialSize", "NullElement", "ComparisonFunction"}; size = 10^4; vals = RandomReal[{-1, 1}, size]; Timing[heap = ResourceFunction["PriorityQueue"][ Thread[defaultNames -> {size, 0., Greater}], vals, "Initialize"];]$

Out[15]=

Now dequeue all elements:

In[16]:=

Timing[sorted = Reap[While [! ResourceFunction["PriorityQueue"][heap, "EmptyQ"], Sow[ResourceFunction["PriorityQueue"][heap, "Dequeue"]]]][[2, 1]];]

Out[16]=

Check that these are actually sorted from largest to smallest:

In[17]:=

Out[17]=

Double the size and check enqueing and dequeing timings:

In[18]:=

(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/60c679fa-b76f-4f0c-af03-f8cc5803a130"]

Out[20]=

Again double the size and check enqueing and dequeing timings:

In[21]:=

(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/a5fadf69-3cbb-4c84-bf5a-3ccf0674d7d3"]

Out[23]=

Possible Issues (1)

Attempting to dequeue from an empty queue gives the default element:

In[24]:=

Out[25]=

Applications (2)

Minimum Spanning Trees: Prim's Method (lazy version) (2)

A minimum spanning tree for a connected graph is a tree that connects every vertex, has no cycles and is of minimal total edge weight. The "lazy" version of Prim's method for computing the minimum spanning tree of a connected, weighted undirected graph works as follows. Start with the most minimal edge. Add its neighbors to a priority queue. Iteratively remove the shortest edge in the queue. If its second vertex is not yet in the tree under construction then add it to the tree and add all its edges to vertices not yet in the tree to the queue. This method was discovered independently by Jarník and Dijkstra. It has algorithmic complexity O(e log e), where e is the number of edges. Here we apply Prim's method for the special case of a complete graph given by a set of points in the plane, with edge weights being the distances between vertices.

Code for Prim's algorithm:

In[26]:=

(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/f626b368-e7e1-4ebd-99da-79e5e32cc047"]

Create random points in the plane:

In[27]:=

Out[28]=

Use Prim's method to compute their minimum spanning tree:

In[29]:=

Out[30]=

Show the graph of the spanning tree:

In[31]:=

Out[31]=

For a graph with e edges, the time complexity of the lazy version using a priority queue is O(e log e). The worst-case space requirement is O(e). In these examples, we work with complete graphs, so with n vertices one has edges.