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.

An immutable priority queue implementation is available in the Immutable submodule.

1

from "priorityqueue" include Priorityqueue

Types

Type declarations included in the PriorityQueue module.

PriorityQueue.PriorityQueue

1

type PriorityQueue<a>

Mutable data structure which maintains a priority order for its elements.

Values

Functions and constants included in the PriorityQueue module.

PriorityQueue.make

1

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:

Returns:

Examples:

1

PriorityQueue.make() // creates a min priority queue of numbers using the compare pervasive

1

PriorityQueue.make(compare=compare, size=32) // creates a min priority queue of numbers using the compare pervasive and an initial size of 32

1

PriorityQueue.make((a, b) => String.length(b) - String.length(a)) // creates a priority queue by string length (longest to shortest)

PriorityQueue.size

1

size : (pq: PriorityQueue<a>) => Number

Gets the number of elements in a priority queue.

Parameters:

Returns:

PriorityQueue.isEmpty

1

isEmpty : (pq: PriorityQueue<a>) => Bool

Determines if the priority queue contains no elements.

Parameters:

Returns:

PriorityQueue.push

1

push : (val: a, pq: PriorityQueue<a>) => Void

Adds a new element to the priority queue.

Parameters:

PriorityQueue.peek

1

peek : (pq: PriorityQueue<a>) => Option<a>

Retrieves the highest priority element in the priority queue. It is not removed from the queue.

Parameters:

Returns:

PriorityQueue.pop

1

pop : (pq: PriorityQueue<a>) => Option<a>

Removes and retrieves the highest priority element in the priority queue.

Parameters:

Returns:

PriorityQueue.drain

1

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:

Returns:

PriorityQueue.fromArray

1
2

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:

Returns:

PriorityQueue.fromList

1

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:

Returns:

PriorityQueue.Immutable

An immutable priority queue implementation.

Types

Type declarations included in the PriorityQueue.Immutable module.

PriorityQueue.Immutable.PriorityQueue

1

type PriorityQueue<a>

Immutable data structure which maintains a priority order for its elements.

Values

Functions and constants included in the PriorityQueue.Immutable module.

PriorityQueue.Immutable.empty

1

empty : PriorityQueue<a>

An empty priority queue with the default compare comparator.

PriorityQueue.Immutable.make

1

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:

Returns:

Examples:

1

PriorityQueue.Immutable.make(compare) // creates a min priority queue of numbers using the compare pervasive

1

PriorityQueue.Immutable.make((a, b) => String.length(b) - String.length(a)) // creates a priority queue by string length (longest to shortest)

PriorityQueue.Immutable.size

1

size : (pq: PriorityQueue<a>) => Number

Gets the number of elements in a priority queue.

Parameters:

Returns:

PriorityQueue.Immutable.isEmpty

1

isEmpty : (pq: PriorityQueue<a>) => Bool

Determines if the priority queue contains no elements.

Parameters:

Returns:

PriorityQueue.Immutable.push

1

push : (val: a, pq: PriorityQueue<a>) => PriorityQueue<a>

Produces a new priority queue by inserting the given element into the given priority queue.

Parameters:

Returns:

PriorityQueue.Immutable.peek

1

peek : (pq: PriorityQueue<a>) => Option<a>

Retrieves the highest priority element in the priority queue. It is not removed from the queue.

Parameters:

Returns:

PriorityQueue.Immutable.pop

1

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:

Returns:

PriorityQueue.Immutable.drain

1

drain : (pq: PriorityQueue<a>) => List<a>

Produces a list of all elements in the priority queue in priority order.

Parameters:

Returns:

PriorityQueue.Immutable.fromList

1

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:

Returns:

PriorityQueue.Immutable.fromArray

1
2

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:

Returns: