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"
are 16, Missing["empty slot"]
"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 jthelement 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.
has the attribute HoldFirst