PriorityQueue
A priority queue is a data structure that maintains elements in a priority order. Elements with higher priority are served before elements with lower priority when extracting from the priority queue.
Edit on GitHubAn immutable priority queue implementation is available in the Immutable submodule.
Added in 0.5.3
No other changes yet.
from "priorityqueue" include PriorityqueueType declarations included in the PriorityQueue module.
type PriorityQueue<a>Mutable data structure which maintains a priority order for its elements.
Functions and constants included in the PriorityQueue module.
Added in 0.5.3
| version | changes |
|---|---|
0.6.0 | Merged with `makeSized`; modified signature to accept size |
make : (?compare: ((a, a) => Number), ?size: Number) => PriorityQueue<a>Creates a new priority queue with a given internal storage size and a comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Generally, you won’t need to care about the storage size of your priority queue and can use the default size.
Parameters:
| param | type | description |
|---|---|---|
?compare | (a, a) => Number | The comparator function used to indicate priority order |
?size | Number | The initial storage size of the priority queue |
?compare: The comparator function used to indicate priority order?size: The initial storage size of the priority queueReturns:
| type | description |
|---|---|
PriorityQueue<a> | An empty priority queue |
PriorityQueue<a>: An empty priority queueExamples:
PriorityQueue.make() // creates a min priority queue of numbers using the compare pervasivePriorityQueue.make(compare=compare, size=32) // creates a min priority queue of numbers using the compare pervasive and an initial size of 32PriorityQueue.make((a, b) => String.length(b) - String.length(a)) // creates a priority queue by string length (longest to shortest)Added in 0.5.3
No other changes yet.
size : (pq: PriorityQueue<a>) => NumberGets the number of elements in a priority queue.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to inspect |
pq: The priority queue to inspectReturns:
| type | description |
|---|---|
Number | The number of elements in the priority queue |
Number: The number of elements in the priority queueAdded in 0.5.3
No other changes yet.
isEmpty : (pq: PriorityQueue<a>) => BoolDetermines if the priority queue contains no elements.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to check |
pq: The priority queue to checkReturns:
| type | description |
|---|---|
Bool | true if the priority queue is empty and false otherwise |
Bool: true if the priority queue is empty and false otherwiseAdded in 0.5.3
No other changes yet.
push : (val: a, pq: PriorityQueue<a>) => VoidAdds a new element to the priority queue.
Parameters:
| param | type | description |
|---|---|---|
val | a | The value to add into the priority queue |
pq | PriorityQueue<a> | The priority queue to update |
val: The value to add into the priority queuepq: The priority queue to updateAdded in 0.5.3
No other changes yet.
peek : (pq: PriorityQueue<a>) => Option<a>Retrieves the highest priority element in the priority queue. It is not removed from the queue.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to inspect |
pq: The priority queue to inspectReturns:
| type | description |
|---|---|
Option<a> | Some(value) containing the highest priority element or None if the priority queue is empty |
Option<a>: Some(value) containing the highest priority element or None if the priority queue is emptyAdded in 0.5.3
No other changes yet.
pop : (pq: PriorityQueue<a>) => Option<a>Removes and retrieves the highest priority element in the priority queue.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to inspect |
pq: The priority queue to inspectReturns:
| type | description |
|---|---|
Option<a> | Some(value) containing the highest priority element or None if the priority queue is empty |
Option<a>: Some(value) containing the highest priority element or None if the priority queue is emptyAdded in 0.5.3
No other changes yet.
drain : (pq: PriorityQueue<a>) => List<a>Clears the priority queue and produces a list of all of the elements in the priority queue in priority order.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to drain |
pq: The priority queue to drainReturns:
| type | description |
|---|---|
List<a> | A list of all elements in the priority in priority order |
List<a>: A list of all elements in the priority in priority orderAdded in 0.5.4
| version | changes |
|---|---|
0.6.0 | Made `compare` a default argument |
fromArray :
(array: Array<a>, ?compare: ((a, a) => Number)) => PriorityQueue<a>Constructs a new priority queue initialized with the elements in the array using a custom comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Parameters:
| param | type | description |
|---|---|---|
array | Array<a> | An array of values used to initialize the priority queue |
?compare | (a, a) => Number | A comparator function used to assign priority to elements |
array: An array of values used to initialize the priority queue?compare: A comparator function used to assign priority to elementsReturns:
| type | description |
|---|---|
PriorityQueue<a> | A priority queue containing the elements from the array |
PriorityQueue<a>: A priority queue containing the elements from the arrayAdded in 0.5.3
| version | changes |
|---|---|
0.6.0 | Made `compare` a default argument |
fromList : (list: List<a>, ?compare: ((a, a) => Number)) => PriorityQueue<a>Constructs a new priority queue initialized with the elements in the list using a custom comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Parameters:
| param | type | description |
|---|---|---|
list | List<a> | A list of values used to initialize the priority queue |
?compare | (a, a) => Number | A comparator function used to assign priority to elements |
list: A list of values used to initialize the priority queue?compare: A comparator function used to assign priority to elementsReturns:
| type | description |
|---|---|
PriorityQueue<a> | A priority queue containing the elements from the list |
PriorityQueue<a>: A priority queue containing the elements from the listAn immutable priority queue implementation.
Added in 0.6.0
| version | changes |
|---|---|
0.5.4 | Originally in `"immutablepriorityqueue"` module |
Type declarations included in the PriorityQueue.Immutable module.
type PriorityQueue<a>Immutable data structure which maintains a priority order for its elements.
Functions and constants included in the PriorityQueue.Immutable module.
Added in 0.6.0
| version | changes |
|---|---|
0.5.4 | Originally in `"immutablepriorityqueue"` module |
empty : PriorityQueue<a>An empty priority queue with the default compare comparator.
Added in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module with `compare` being a required argument |
make : (?compare: ((a, a) => Number)) => PriorityQueue<a>Creates a new priority queue with a comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Parameters:
| param | type | description |
|---|---|---|
?compare | (a, a) => Number | The comparator function used to indicate priority order |
?compare: The comparator function used to indicate priority orderReturns:
| type | description |
|---|---|
PriorityQueue<a> | An empty priority queue |
PriorityQueue<a>: An empty priority queueExamples:
PriorityQueue.Immutable.make(compare) // creates a min priority queue of numbers using the compare pervasivePriorityQueue.Immutable.make((a, b) => String.length(b) - String.length(a)) // creates a priority queue by string length (longest to shortest)Added in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
size : (pq: PriorityQueue<a>) => NumberGets the number of elements in a priority queue.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to inspect |
pq: The priority queue to inspectReturns:
| type | description |
|---|---|
Number | The number of elements in the priority queue |
Number: The number of elements in the priority queueAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
isEmpty : (pq: PriorityQueue<a>) => BoolDetermines if the priority queue contains no elements.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to check |
pq: The priority queue to checkReturns:
| type | description |
|---|---|
Bool | true if the priority queue is empty and false otherwise |
Bool: true if the priority queue is empty and false otherwiseAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
push : (val: a, pq: PriorityQueue<a>) => PriorityQueue<a>Produces a new priority queue by inserting the given element into the given priority queue.
Parameters:
| param | type | description |
|---|---|---|
val | a | The value to add into the priority queue |
pq | PriorityQueue<a> | The priority queue |
val: The value to add into the priority queuepq: The priority queueReturns:
| type | description |
|---|---|
PriorityQueue<a> | A new priority queue with the given element inserted |
PriorityQueue<a>: A new priority queue with the given element insertedAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
peek : (pq: PriorityQueue<a>) => Option<a>Retrieves the highest priority element in the priority queue. It is not removed from the queue.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to inspect |
pq: The priority queue to inspectReturns:
| type | description |
|---|---|
Option<a> | Some(value) containing the highest priority element or None if the priority queue is empty |
Option<a>: Some(value) containing the highest priority element or None if the priority queue is emptyAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
pop : (pq: PriorityQueue<a>) => PriorityQueue<a>Produces a new priority queue without the highest priority element in the given priority queue. If the input priority queue is empty, this function will return it.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue |
pq: The priority queueReturns:
| type | description |
|---|---|
PriorityQueue<a> | A new priority queue without the highest priority element |
PriorityQueue<a>: A new priority queue without the highest priority elementAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module |
drain : (pq: PriorityQueue<a>) => List<a>Produces a list of all elements in the priority queue in priority order.
Parameters:
| param | type | description |
|---|---|---|
pq | PriorityQueue<a> | The priority queue to drain |
pq: The priority queue to drainReturns:
| type | description |
|---|---|
List<a> | A list of all elements in the priority in priority order |
List<a>: A list of all elements in the priority in priority orderAdded in 0.6.0
| version | changes |
|---|---|
0.5.3 | Originally in `"immutablepriorityqueue"` module with `compare` being a required argument |
fromList : (list: List<a>, ?compare: ((a, a) => Number)) => PriorityQueue<a>Constructs a new priority queue initialized with the elements in the list using a custom comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Parameters:
| param | type | description |
|---|---|---|
list | List<a> | A list of values used to initialize the priority queue |
?compare | (a, a) => Number | A comparator function used to assign priority to elements |
list: A list of values used to initialize the priority queue?compare: A comparator function used to assign priority to elementsReturns:
| type | description |
|---|---|
PriorityQueue<a> | A priority queue containing the elements from the list |
PriorityQueue<a>: A priority queue containing the elements from the listAdded in 0.6.0
| version | changes |
|---|---|
0.5.4 | Originally in `"immutablepriorityqueue"` module with `compare` being a required argument |
fromArray :
(array: Array<a>, ?compare: ((a, a) => Number)) => PriorityQueue<a>Constructs a new priority queue initialized with the elements in the array using a custom comparator function, which is used to determine priority of elements. The comparator function takes two elements and must return 0 if both share priority, a positive number if the first has greater priority, and a negative number if the first has less priority.
Parameters:
| param | type | description |
|---|---|---|
array | Array<a> | An array of values used to initialize the priority queue |
?compare | (a, a) => Number | A comparator function used to assign priority to elements |
array: An array of values used to initialize the priority queue?compare: A comparator function used to assign priority to elementsReturns:
| type | description |
|---|---|
PriorityQueue<a> | A priority queue containing the elements from the array |
PriorityQueue<a>: A priority queue containing the elements from the array