# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Provide an indexed priority queue data structure with its standard operations

Contributed by:
Daniel Lichtblau

ResourceFunction["IndexedQueue"][] returns an indexed priority queue initialized with default settings. | |

ResourceFunction["IndexedQueue"][{"InitialSize"→ returns an indexed queue initialized to have length | |

ResourceFunction["IndexedQueue"][ returns an indexed queue initialized with parameters in | |

ResourceFunction["IndexedQueue"][ returns a list containing the index and value of the topmost element in | |

ResourceFunction["IndexedQueue"][ places | |

ResourceFunction["IndexedQueue"][ removes the element indexed by | |

ResourceFunction["IndexedQueue"][ replaces the current value of element | |

ResourceFunction["IndexedQueue"][ gives the number of elements in | |

ResourceFunction["IndexedQueue"][ gives the value of the topmost element in | |

ResourceFunction["IndexedQueue"][ gives the index of the topmost element in | |

ResourceFunction["IndexedQueue"][ gives the value associated to the element indexed by |

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

Another application is to find an approximate minimal vertex cover for a graph using an efficient greedy method.

Indexed queues can be used in the same way as ordinary priority queues, with the added capabilities of altering index values dynamically and removing indicies other than the topmost.

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

This implementation of priority queues uses binary heaps along with lists from key index to queue position and vice versa.

In binary heap implementations such as this one, each element in a priority queue has either zero, one or two children. If the *j*^{th}element has children, they will be located at positions 2*j* and 2*j*+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.

Generally, an indexed 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["IndexedQueue"] has the attribute HoldFirst.

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

Check the size:

In[1]:= |

Out[1]= |

Check the value of the largest element:

In[2]:= |

Out[2]= |

Add 80 more random values to the heap:

Recheck length and largest value:

In[3]:= |

Out[3]= |

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

In[4]:= |

Out[4]= |

Check that it is indeed empty:

In[5]:= |

Out[5]= |

An alternative check is that the length is zero:

In[6]:= |

Out[6]= |

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

In[7]:= |

Out[7]= |

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

Now sort them in dictionary order by dequeuing, returning both original positions and values:

In[8]:= |

Out[8]= |

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

Use a queue to enqueue 10000 random values:

In[9]:= |

Out[9]= |

Now dequeue all elements:

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

Double the size and check enqueing and dequeing timings:

In[12]:= |

Out[12]= |

Again double the size and check enqueing and dequeing timings:

In[13]:= |

Out[13]= |

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

Out[13]= |

IndexedQueue has the same asymptotic complexity as the resource function PriorityQueue, but it has a larger constant factor due to the extra work in handling enqueuing and dequeuing.

Define a timing test for purposes of comparing IndexedQueue with PriorityQueue:

Create a set of 10000 random real values:

Time enqueuing and dequeuing using IndexedQueue:

In[14]:= |

Out[14]= |

Compare to enqueuing and dequeuing using PriorityQueue:

In[15]:= |

Out[15]= |

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 "eager" version of Prim's method for computing the minimum spanning tree of a connected, weighted undirected graph works as follows. Start with any vertex. For any edge from that vertex, enqueue the vertex it connects to with value set to the edge weight. Iteratively remove from the queue the vertex of lowest edge weight and add it to the spanning tree under construction. Then iterate over the vertices connected to that vertex. Ignore those that already are in the tree. Enqueue with edge weight those that are not already in the queue. For a vertex currently in the queue, update the value if the edge weight is less than that which was previously associated to that vertex. For a graph of *V* vertices and *E* edges the complexity is *O*(*E* log *V*).

Code for the eager form of Prim's algorithm, specialized to a complete graph with edge weights as pairwise distances between planar points:

Create an example set of points:

In[16]:= |

Out[16]= |

Find the minimal spanning tree and total edge weight:

In[17]:= |

Out[17]= |

Check the total edge weight:

In[18]:= |

Out[18]= |

Plot the spanning tree:

In[19]:= |

Out[19]= |

Double the vertex count and repeat:

In[20]:= |

Out[20]= |

Double again:

In[21]:= |

Out[21]= |

Using the built-in Prim method is an order of magnitude faster:

In[22]:= |

Out[22]= |

A vertex cover for a graph is a subset of vertices that hit all edges. Stated differently, every edge must have at least one endpoint in the cover. A cover with the minimal number of vertices is called a minimal cover. An approximate minimal cover can be found efficiently using a greedy algorithm as follows. First choose a vertex that hits the most edges, and remove those edges from consideration. This means we decrement the edge counts of all vertices connected to the one that was selected. Iteratively remove a vertex hitting the greatest number of remaining edges, and decrement edge counts of vertices connected to the one selected. Continue until no edges remain unhit. This can be implemented efficiently using an indexed priority queue.

Implement a greedy-with-updates approximate vertex cover using an indexed queue:

Create a random graph with 30 vertices and 80 edges:

In[23]:= |

Out[23]= |

Find an approximate vertex cover for this graph:

In[24]:= |

Out[24]= |

Check that it is a cover:

In[25]:= |

Out[25]= |

Compare the length to the actual minimal cover length:

In[26]:= |

Out[26]= |

Time this for a much larger random graph:

In[27]:= |

Out[27]= |

Check that it is a cover and find the length:

Out[27]= |

Out[27]= |

A method used in the resource function ApproximateVertexCover is substantially similar to the one above:

In[28]:= |

Out[28]= |

- WilliamFiset YouTube–Indexed Priority Queue (UPDATED) | Data Structures
- Implementing the Decrease-Key Operation for Min-Heaps–BaeldungCS

- 1.0.0 – 10 May 2021

This work is licensed under a Creative Commons Attribution 4.0 International License