7.8
7 Binary Heaps
| (require data/heap) | package: data-lib |
Binary heaps are a simple implementation of priority queues.
Operations on binary heaps are not thread-safe.
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>
Returns #t if x is a heap, #f otherwise.
Examples:
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
Adds each v to the heap.
Examples:
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-add-all! heap-12 heap-1) > (heap-add-all! heap-12 heap-2) > (heap-count heap-12) 16
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
(heap-remove-min! h) → void?
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?]) → boolean?
h : heap? v : any/c same? : (-> any/c any/c any/c) = equal?
Removes v from the heap h if it exists,
and returns #t if the removal was successful, #f otherwise.
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") #t
> (for/list ([a (in-heap a-heap)]) a)
'("a"
"bifur"
"bofur"
"bombur"
"c"
"dori"
"dwalin"
"fili"
"fili"
"gloin"
"nori"
"oin"
"ori"
"thorin")
Builds a heap with the elements from items. The vector is not
modified.
Examples:
procedure
(heap->vector h) → vector?
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")
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
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")