← Index

x/type/pq

A binary-heap priority queue, homed on the Pq class.

The heap structure under the queue name – Heap is the GC class. Comparator contract matches List sort: (cmp a b) -> #t when a comes strictly first.

Class Pq

A binary-heap priority queue over a comparator: push!/pop! O(log n), peek O(1). (cmp a b) -> #t when a comes strictly first (the List sort contract).

store

Member: data carried by a Pq instance.

cmp

Member: data carried by a Pq instance.

(Pq make cmp)

An empty priority queue ordered by cmp.

Parameters:

• cmp : CALLABLE — Comparison: (cmp a b) -> #t when a comes strictly first

Returns: Pq — A new empty queue

Examples:

((Pq make (fn (_ a b) (< a b))) length) => 0

(%sift-up! i)

Instance method: called on a Pq instance.

(%sift-down! i)

Instance method: called on a Pq instance.

(push! v)

Enqueue a value: O(log n). Returns the queue for chaining.

Instance method: called on a Pq instance.

Parameters:

• v : ANY — Value to enqueue

Returns: Pq — self

(peek)

The front value (the one pop! would return), without removing it; raises tag ‘value when empty.

Instance method: called on a Pq instance.

Returns: ANY — The front value

(pop!)

Remove and return the front value: O(log n); raises tag ‘value when empty.

Instance method: called on a Pq instance.

Returns: ANY — The front value

Examples:

(let ((q (Pq make (fn (_ a b) (< a b))))) (q push! 9) (q push! 4) (list (q pop!) (q pop!))) => (4 9)

(length)

How many values are queued.

Instance method: called on a Pq instance.

Returns: INT — The count

(empty?)

Is the queue empty?

Instance method: called on a Pq instance.

Returns: BOOL — #t when nothing is queued