8.15
7 Binary Heaps
| (require data/heap) | package: data-lib |
Binary heaps are a simple implementation of priority queues. For a heap of n elements, heap-add! and heap-remove-min! take O(log n) time per added or removed element, while heap-min and heap-count take constant time; heap-remove! takes O(n) time, and heap-remove-eq! takes O(log n) time on average; heap-sort! takes O(n log n) time.
Operations on binary heaps are not thread-safe.
All functions are also provided by data/heap/unsafe without contracts.
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.
This operation takes O(n) time—
Examples:
procedure
(heap-remove-eq! h v) → boolean?
h : heap? v : any/c
Removes v from the heap h if it exists according to eq?,
and returns #t if the removal was successful, #f otherwise.
This operation takes O(log n) time, plus the indexing cost (which is O(1) on average,
but O(n) in the worst case). The heap must not contain duplicate
elements according to eq?, otherwise it may not be possible to remove all duplicates
(see the example below).
Examples:
> (define h (make-heap string<=?)) > (define elt1 "123") > (define elt2 "abcxyz") > (heap-add! h elt1 elt2) ; The element is not found because no element of the heap is `eq?` ; to the provided value: > (heap-remove-eq! h (string-append "abc" "xyz")) #f
> (heap->vector h) '#("123" "abcxyz")
; But this succeeds: > (heap-remove-eq! h elt2) #t
> (heap->vector h) '#("123")
; Removing duplicate elements (according to `eq?`) may fail: > (heap-add! h elt2 elt2) > (heap->vector h) '#("123" "abcxyz" "abcxyz")
> (heap-remove-eq! h elt2) #t
> (heap-remove-eq! h elt2) #f
> (heap->vector h) '#("123" "abcxyz")
; But we can resort to the more general `heap-remove!`: > (heap-remove! h elt2 #:same? string=?) #t
> (heap->vector h) '#("123")
Added in version 7.8.0.5 of package data-lib.
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 "flock" "hatful" "deal" "batch" "lot" "good deal")) > (heap-sort! terms string<=?) > terms '#("batch" "deal" "flock" "good deal" "hatful" "lot")