(std priority-queue)

Reference

Overview

A persistent priority queue, least priority first, with a transient and a builder.

(import (std priority-queue))

(def q (priorityqueue-add (priorityqueue-add (priorityqueue-empty) "write" 2) "plan" 1))
(priorityqueue-peek q)                     ; (Some (Tuple "plan" 1))
(priorityqueue-peek (priorityqueue-remove-min q))   ; (Some (Tuple "write" 2))
(priorityqueue-peek q)                     ; still (Some (Tuple "plan" 1))

A (PriorityQueue a p) holds elements of type a under priorities of type p, and gives back the least priority first. A queue is a value: adding to it or removing from it answers a new queue, and the old one is unchanged.

The structure. A pairing heap. Peeking, adding and merging two queues are O(1). Removing the least is O(log n) amortised. A queue made from n entries at once, by list->priorityqueue, priorityqueue-add-all or a builder, takes O(n).

Using a queue again. The amortised bound holds when each queue is used once: you go on with the result and drop the queue you had. n adds leave a queue whose next removal walks all n entries, and that removal pays for the adds. A queue kept and removed from again pays it again each time. priorityqueue-balance rebuilds a queue in O(n) so that every removal from it is O(log n), and is the thing to call before a queue is kept as the start of many others. A queue made from many entries at once is balanced already.

Elements and priorities. The queue orders priorities, not elements, so the element type needs no order. priorityqueue-empty orders priorities by their Ord; priorityqueue-by takes a comparison, for any other order or a type without Ord.

Equal priorities come out in the order they were added to the queue. After priorityqueue-merge, entries of the two queues with equal priorities come out in an order that is fixed but not specified.

A transient is a queue that changes in place, for many changes in a row: priorityqueue->transientpriorityqueue makes one, and transientpriorityqueue->priorityqueue gives a queue of what it holds in O(1). It copies a cell of the queue it came from once, the first time an operation reaches it, and changes its own cells without copying: adding allocates one cell, and taking the least allocates nothing. Freezing does not balance: call priorityqueue-balance on the queue before using it again many times. A transient is not safe to use from two threads at once.

A builder collects entries and makes a queue of them in O(n).

For a queue used in one place and never shared, (std mutable heap) is faster: it is an array, and has no cells to allocate.

Traits. PriorityQueue implements Collection and Iterable over (Tuple a p), in the order the entries come out; Eq, by the entries in that order; and Written and Displayed.

See also: PriorityQueue, priorityqueue-empty, priorityqueue-add, priorityqueue-pop, TransientPriorityQueue, PriorityQueueBuilder

Reference

Types

Functions

Types

PriorityQueue

record ↑ Types

A persistent priority queue of elements %a under priorities %p, least first.

%a
The element type, which needs no order.
%p
The priority type.

See also: priorityqueue-empty, priorityqueue-by, TransientPriorityQueue

TransientPriorityQueue

record ↑ Types

A priority queue that changes in place, made from a PriorityQueue and turned back into one in O(1).

%a
The element type.
%p
The priority type.
(def t (priorityqueue->transientpriorityqueue q))
(transientpriorityqueue-add! t "urgent" 0)
(transientpriorityqueue-pop! t)            ; (Some (Tuple "urgent" 0))
(transientpriorityqueue->priorityqueue t)

See also: priorityqueue->transientpriorityqueue, transientpriorityqueue->priorityqueue, transientpriorityqueue-add!, transientpriorityqueue-pop!

PriorityQueueBuilder

record ↑ Types

Collects entries one at a time, and makes a PriorityQueue of them in O(n).

%a
The element type.
%p
The priority type.

See also: priorityqueuebuilder-empty, priorityqueuebuilder-add!, priorityqueuebuilder->priorityqueue

PriorityQueueTree

union ↑ Types

The tree of a queue. Opaque; exported because functions an importer inlines name it.

%a
The element type.
%p
The priority type.

PriorityQueueCell

record ↑ Types

One entry of a queue’s tree. Opaque; exported because functions an importer inlines name it.

%a
The element type.
%p
The priority type.

PriorityQueueOwner

record ↑ Types

What a transient owns its cells by. Opaque; exported because functions an importer inlines name it.

Functions

priorityqueue-empty

function ↑ Functions

(: priorityqueue-empty (-> (PriorityQueue %a %p)))
(priorityqueue-empty)

An empty queue, ordering priorities by their Ord.

returns
An empty queue.

See also: priorityqueue-by, list->priorityqueue

priorityqueue-by

function ↑ Functions

(: priorityqueue-by (-> (-> %p %p int) (PriorityQueue %a %p)))
(priorityqueue-by order)

An empty queue, ordering priorities by a comparison.

order
Negative when its first argument comes out first, 0 for equal, positive otherwise.
returns
An empty queue. Every queue made from it orders the same way.
(priorityqueue-by (fun (a b) (compare b a)))   ; the greatest priority first

See also: priorityqueue-empty

priorityqueue-length

function ↑ Functions

(: priorityqueue-length (-> (PriorityQueue %a %p) int))
(priorityqueue-length q)

How many entries a queue holds. O(1).

q
The queue.
returns
The number of entries.

See also: priorityqueue-empty?

priorityqueue-empty?

function ↑ Functions

(: priorityqueue-empty? (-> (PriorityQueue %a %p) bool))
(priorityqueue-empty? q)

Whether a queue holds nothing.

q
The queue.
returns
#t when it is empty.

See also: priorityqueue-length

priorityqueue-peek

function ↑ Functions

(: priorityqueue-peek (-> (PriorityQueue %a %p) (Option (Tuple %a %p))))
(priorityqueue-peek q)

The entry that comes out first, left in the queue. O(1).

q
The queue.
returns
(Some (Tuple element priority)), or None when the queue is empty.

See also: priorityqueue-pop, priorityqueue-remove-min

priorityqueue-add

function ↑ Functions

(: priorityqueue-add (-> (PriorityQueue %a %p) %a %p (PriorityQueue %a %p)))
(priorityqueue-add q x p)

A queue with one more entry. O(1).

q
The queue, which is left as it was.
x
The element.
p
Its priority.
returns
A new queue.

See also: priorityqueue-add-all, transientpriorityqueue-add!

priorityqueue-add-all

function ↑ Functions

(: priorityqueue-add-all (-> (PriorityQueue %a %p) (List (Tuple %a %p)) (PriorityQueue %a %p)))
(priorityqueue-add-all q entries)

A queue with the entries of a list added. O(n) for n entries.

q
The queue, which is left as it was.
entries
(Tuple element priority) pairs. Equal priorities come out in this order, after those already in q.
returns
A new queue.

See also: priorityqueue-add, list->priorityqueue

priorityqueue-merge

function ↑ Functions

(: priorityqueue-merge (-> (PriorityQueue %a %p) (PriorityQueue %a %p) (PriorityQueue %a %p)))
(priorityqueue-merge a b)

One queue with the entries of two. O(1).

a
A queue, whose order the result has.
b
A queue with the same order as a.
returns
A new queue. Neither argument is changed.

The result orders by a’s comparison, and b must have been made with the same one: a comparison is a function, and two functions cannot be compared, so this is not checked. When they differ, add the entries of b instead: (priorityqueue-add-all a (priorityqueue->unordered-list b)).

priorityqueue-pop

function ↑ Functions

(: priorityqueue-pop (-> (PriorityQueue %a %p) (Option (Tuple %a %p (PriorityQueue %a %p)))))
(priorityqueue-pop q)

The entry that comes out first, and the queue without it. O(log n) amortised.

q
The queue, which is left as it was.
returns
(Some (Tuple element priority rest)), or None when the queue is empty.
(match (priorityqueue-pop q)
  ((Some (Tuple task priority rest)) (run task) rest)
  (None q))

See also: priorityqueue-peek, priorityqueue-remove-min

priorityqueue-remove-min

function ↑ Functions

(: priorityqueue-remove-min (-> (PriorityQueue %a %p) (PriorityQueue %a %p)))
(priorityqueue-remove-min q)

The queue without the entry that comes out first. O(log n) amortised.

q
The queue, which is left as it was.
returns
A new queue, or q itself when it is empty.

The cost is that of linking the children of the entry removed: one for each entry added since the last removal. On a queue that is removed from only once, the adds have paid for it. On a queue removed from again and again, call priorityqueue-balance first.

See also: priorityqueue-pop, priorityqueue-peek, priorityqueue-balance

priorityqueue-balance

function ↑ Functions

(: priorityqueue-balance (-> (PriorityQueue %a %p) (PriorityQueue %a %p)))
(priorityqueue-balance q)

The same queue, rebuilt so that removing the least is O(log n) from it however often it is used. O(n).

q
The queue, which is left as it was.
returns
A balanced queue with the same entries, which come out in the same order. q itself when it is balanced already.
;; A queue kept as the start of many searches:
(def start (priorityqueue-balance (loop (:for job jobs)
                                        (:acc q (folding (priorityqueue-empty)
                                                         (priorityqueue-add q job (cost job)))))))

The cells are rebuilt as a tournament: neighbours linked, then the results linked in pairs, until one is left. The root then has about log2(n) children, and so has every cell below it.

See also: priorityqueue-balanced?, priorityqueue-remove-min

priorityqueue-balanced?

function ↑ Functions

(: priorityqueue-balanced? (-> (PriorityQueue %a %p) bool))
(priorityqueue-balanced? q)

Whether a queue came out of priorityqueue-balance or a build from many entries, and is unchanged since.

q
The queue.
returns
#t when it is balanced. #f says only that it may not be.

See also: priorityqueue-balance

list->priorityqueue

function ↑ Functions

(: list->priorityqueue (-> (List (Tuple %a %p)) (PriorityQueue %a %p)))
(list->priorityqueue entries)

A queue of the entries of a list, ordering priorities by their Ord. O(n).

entries
(Tuple element priority) pairs. Equal priorities come out in this order.
returns
A new queue.

For another order, add the entries to an empty queue with that order: (priorityqueue-add-all (priorityqueue-by order) entries).

See also: priorityqueue-add-all, priorityqueue->list

priorityqueue->list

function ↑ Functions

(: priorityqueue->list (-> (PriorityQueue %a %p) (List (Tuple %a %p))))
(priorityqueue->list q)

Every entry, in the order they come out. O(n log n).

q
The queue, which is left as it was.
returns
A list of (Tuple element priority) pairs.

See also: priorityqueue->unordered-list

priorityqueue->unordered-list

function ↑ Functions

(: priorityqueue->unordered-list (-> (PriorityQueue %a %p) (List (Tuple %a %p))))
(priorityqueue->unordered-list q)

Every entry, in no particular order. O(n).

q
The queue.
returns
A list of (Tuple element priority) pairs.

See also: priorityqueue->list

priorityqueue->str

function ↑ Functions

(: priorityqueue->str (-> (PriorityQueue %a %p) string))
(priorityqueue->str q)

Deprecated: use displayed. A queue as text: #priorityqueue(element priority …), in the order the entries come out.

q
The queue.
returns
The text.
(displayed (list->priorityqueue (list (Tuple "b" 2) (Tuple "a" 1))))
; "#priorityqueue(a 1 b 2)"

transientpriorityqueue-empty

function ↑ Functions

(: transientpriorityqueue-empty (-> (TransientPriorityQueue %a %p)))
(transientpriorityqueue-empty)

An empty transient, ordering priorities by their Ord.

returns
An empty transient.

See also: transientpriorityqueue-by, priorityqueue->transientpriorityqueue

transientpriorityqueue-by

function ↑ Functions

(: transientpriorityqueue-by (-> (-> %p %p int) (TransientPriorityQueue %a %p)))
(transientpriorityqueue-by order)

An empty transient, ordering priorities by a comparison.

order
Negative when its first argument comes out first, 0 for equal, positive otherwise.
returns
An empty transient.

See also: transientpriorityqueue-empty, priorityqueue-by

priorityqueue->transientpriorityqueue

function ↑ Functions

(: priorityqueue->transientpriorityqueue (-> (PriorityQueue %a %p) (TransientPriorityQueue %a %p)))
(priorityqueue->transientpriorityqueue q)

A transient holding what a queue holds. O(1).

q
The queue, which no change to the transient affects.
returns
A new transient with q's order.

See also: transientpriorityqueue->priorityqueue

transientpriorityqueue->priorityqueue

function ↑ Functions

(: transientpriorityqueue->priorityqueue (-> (TransientPriorityQueue %a %p) (PriorityQueue %a %p)))
(transientpriorityqueue->priorityqueue t)

A queue of what a transient holds. O(1).

t
The transient, which may go on being used.
returns
A new queue, which no later change to t affects.

The transient goes on with a new owner, so its next changes copy what they reach before changing it, as they did when it was made. The queue is not balanced, which would make this O(n): call priorityqueue-balance on it before using it again many times.

See also: priorityqueue->transientpriorityqueue

transientpriorityqueue-length

function ↑ Functions

(: transientpriorityqueue-length (-> (TransientPriorityQueue %a %p) int))
(transientpriorityqueue-length t)

How many entries a transient holds. O(1).

t
The transient.
returns
The number of entries.

transientpriorityqueue-empty?

function ↑ Functions

(: transientpriorityqueue-empty? (-> (TransientPriorityQueue %a %p) bool))
(transientpriorityqueue-empty? t)

Whether a transient holds nothing.

t
The transient.
returns
#t when it is empty.

transientpriorityqueue-peek

function ↑ Functions

(: transientpriorityqueue-peek (-> (TransientPriorityQueue %a %p) (Option (Tuple %a %p))))
(transientpriorityqueue-peek t)

The entry that comes out first, left in the transient. O(1).

t
The transient.
returns
(Some (Tuple element priority)), or None when it is empty.

See also: transientpriorityqueue-pop!

transientpriorityqueue-add!

function ↑ Functions

(: transientpriorityqueue-add! (-> (TransientPriorityQueue %a %p) %a %p void))
(transientpriorityqueue-add! t x p)

Adds an entry to a transient, in place. O(1).

t
The transient.
x
The element.
p
Its priority.

See also: transientpriorityqueue-add-all!, transientpriorityqueue-pop!

transientpriorityqueue-add-all!

function ↑ Functions

(: transientpriorityqueue-add-all! (-> (TransientPriorityQueue %a %p) (List (Tuple %a %p)) void))
(transientpriorityqueue-add-all! t entries)

Adds the entries of a list to a transient, in place. O(n) for n entries.

t
The transient.
entries
(Tuple element priority) pairs. Equal priorities come out in this order, after those already in t.

See also: transientpriorityqueue-add!

transientpriorityqueue-pop!

function ↑ Functions

(: transientpriorityqueue-pop! (-> (TransientPriorityQueue %a %p) (Option (Tuple %a %p))))
(transientpriorityqueue-pop! t)

Removes the entry that comes out first from a transient, in place. O(log n) amortised.

t
The transient.
returns
(Some (Tuple element priority)), or None when it is empty, which leaves it as it was.

See also: transientpriorityqueue-peek, transientpriorityqueue-add!

priorityqueuebuilder-empty

function ↑ Functions

(: priorityqueuebuilder-empty (-> (PriorityQueueBuilder %a %p)))
(priorityqueuebuilder-empty)

An empty builder, ordering priorities by their Ord.

returns
An empty builder.

See also: priorityqueuebuilder-by

priorityqueuebuilder-by

function ↑ Functions

(: priorityqueuebuilder-by (-> (-> %p %p int) (PriorityQueueBuilder %a %p)))
(priorityqueuebuilder-by order)

An empty builder, ordering priorities by a comparison.

order
Negative when its first argument comes out first, 0 for equal, positive otherwise.
returns
An empty builder.

See also: priorityqueuebuilder-empty

priorityqueuebuilder-add!

function ↑ Functions

(: priorityqueuebuilder-add! (-> (PriorityQueueBuilder %a %p) %a %p void))
(priorityqueuebuilder-add! b x p)

Adds an entry to a builder. O(1).

b
The builder.
x
The element.
p
Its priority.

See also: priorityqueuebuilder->priorityqueue

priorityqueuebuilder-length

function ↑ Functions

(: priorityqueuebuilder-length (-> (PriorityQueueBuilder %a %p) int))
(priorityqueuebuilder-length b)

How many entries a builder has been given.

b
The builder.
returns
The number of entries.

priorityqueuebuilder->priorityqueue

function ↑ Functions

(: priorityqueuebuilder->priorityqueue (-> (PriorityQueueBuilder %a %p) (PriorityQueue %a %p)))
(priorityqueuebuilder->priorityqueue b)

A queue of a builder’s entries. O(n).

b
The builder, which keeps its entries and may be added to and built again.
returns
A new, balanced queue. Equal priorities come out in the order they were added.

See also: priorityqueuebuilder-add!