6.1.1

7Binary Heaps

 (require data/heap) package: data-lib

Binary heaps are a simple implementation of priority queues.

Operations on binary heaps are not thread-safe.

 procedure(make-heap <=?) → heap? <=? : (-> any/c any/c any/c)
Makes a new empty heap using <=? to order elements.

Examples:

> (define a-heap-of-strings (make-heap string<=?))
> a-heap-of-strings

#<heap>

; With structs:
> (struct node (name val))
 > (define (node<=? x y) (<= (node-val x) (node-val y)))
> (define a-heap-of-nodes (make-heap node<=?))
> a-heap-of-nodes

#<heap>

 procedure(heap? x) → boolean? x : any/c
Returns #t if x is a heap, #f otherwise.

Examples:

 > (heap? (make-heap <=)) #t > (heap? "I am not a heap") #f

 procedure h : heap?
Returns the number of elements in the heap.

Examples:

> (define a-heap (make-heap <=))
> (heap-add-all! a-heap '(7 3 9 1 13 21 15 31))
> (heap-count a-heap)

8

 procedure(heap-add! h v ...) → void? h : heap? v : any/c
Adds each v to the heap.

Examples:

> (define a-heap (make-heap <=))

 procedure(heap-add-all! h v) → void? h : heap? v : (or/c list? vector? heap?)
Adds each element contained in v to the heap, leaving v unchanged.

Examples:

> (define heap-1 (make-heap <=))
> (define heap-2 (make-heap <=))
> (define heap-12 (make-heap <=))
> (heap-add-all! heap-1 '(3 1 4 1 5 9 2 6))
> (heap-add-all! heap-2 #(2 7 1 8 2 8 1 8))
> (heap-count heap-12)

16

 procedure(heap-min h) → any/c h : heap?
Returns the least element in the heap h, according to the heap’s ordering. If the heap is empty, an exception is raised.

Examples:

> (define a-heap (make-heap string<=?))
 > (heap-add! a-heap "sneezy" "sleepy" "dopey" "doc" "happy" "bashful" "grumpy")
> (heap-min a-heap)

"bashful"

; Taking the min of the empty heap is an error:
> (heap-min (make-heap <=))

heap-min: empty heap

 procedure h : heap?
Removes the least element in the heap h. If the heap is empty, an exception is raised.

Examples:

> (define a-heap (make-heap string<=?))
 > (heap-add! a-heap "fili" "fili" "oin" "gloin" "thorin" "dwalin" "balin" "bifur" "bofur" "bombur" "dori" "nori" "ori")
> (heap-min a-heap)

"balin"

> (heap-remove-min! a-heap)
> (heap-min a-heap)

"bifur"

 procedure(heap-remove! h v [#:same? same?]) → void? h : heap? v : any/c same? : (-> any/c any/c any/c) = equal?
Removes v from the heap h if it exists.

Examples:

> (define a-heap (make-heap string<=? string=?))

make-heap: arity mismatch;

the expected number of arguments does not match the given

number

expected: 1

given: 2

arguments...:

#<procedure:string<=?>

#<procedure:string=?>

> (heap-add! a-heap "a" "b" "c")
> (heap-remove! a-heap "b")
> (for/list ([a (in-heap a-heap)]) a)
 '("a" "bifur" "bofur" "bombur" "c" "dori" "dwalin" "fili" "fili" "gloin" "nori" "oin" "ori" "thorin")

 procedure(vector->heap <=? items) → heap? <=? : (-> any/c any/c any/c) items : vector?
Builds a heap with the elements from items. The vector is not modified.

Examples:

> (struct item (val frequency))
 > (define (item<=? x y) (<= (item-frequency x) (item-frequency y)))
 > (define some-sample-items (vector (item #\a 17) (item #\b 12) (item #\c 19)))
> (define a-heap (vector->heap item<=? some-sample-items))

 procedure h : heap?
Returns a vector containing the elements of heap h in the heap’s order. The heap is not modified.

Examples:

> (define word-heap (make-heap string<=?))
> (heap-add! word-heap "pile" "mound" "agglomerate" "cumulation")
> (heap->vector word-heap)

'#("agglomerate" "cumulation" "mound" "pile")

 procedure(heap-copy h) → heap? h : heap?
Makes a copy of heap h.

Examples:

> (define word-heap (make-heap string<=?))
> (heap-add! word-heap "pile" "mound" "agglomerate" "cumulation")
> (define a-copy (heap-copy word-heap))
> (heap-remove-min! a-copy)
> (heap-count word-heap)

4

> (heap-count a-copy)

3

 procedure(in-heap/consume! heap) → sequence? heap : heap?
Returns a sequence equivalent to heap, maintaining the heap’s ordering. The heap is consumed in the process. Equivalent to repeated calling heap-min, then heap-remove-min!.

Examples:

> (define h (make-heap <=))
> (heap-add-all! h '(50 40 10 20 30))
 > (for ([x (in-heap/consume! h)]) (displayln x))
 10 20 30 40 50
> (heap-count h)

0

 procedure(in-heap heap) → sequence? heap : heap?
Returns a sequence equivalent to heap, maintaining the heap’s ordering. Equivalent to in-heap/consume! except the heap is copied first.

Examples:

> (define h (make-heap <=))
> (heap-add-all! h '(50 40 10 20 30))
 > (for ([x (in-heap h)]) (displayln x))
 10 20 30 40 50
> (heap-count h)

5

 procedure(heap-sort! v <=?) → void? v : (and/c vector? (not/c immutable?)) <=? : (-> any/c any/c any/c)
Sorts vector v using the comparison function <=?.

Examples:

> (define terms (vector "batch" "deal" "flock" "good deal" "hatful" "lot"))
> (heap-sort! terms string<=?)
> terms

'#("batch" "deal" "flock" "good deal" "hatful" "lot")