← 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

Field: data carried by a Pq instance.

cmp

Field: 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

Examples:

((((Pq make (fn (_ a b) (< a b))) push! 5) push! 2) peek) => 2

(peek)

The front value (the one pop! would return), without removing it; raises a label ‘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! 1) (q push! 7) (q peek)) => 7

(pop!)

Remove and return the front value: O(log n); raises a label ‘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: INTEGER — The count

Examples:

((((Pq make (fn (_ a b) (< a b))) push! 1) push! 1) length) => 2

(empty?)

Is the queue empty?

Instance method: called on a Pq instance.

Returns: BOOL — #t when nothing is queued

Examples:

((Pq make (fn (_ a b) (< a b))) empty?) => #t