== heap
Mutable heap with priority-queue operations and O(1) membership-testing
[[toc:]]
=== {{heap}}
heap
The heap data-structure
; >? : Greater-than relation for keys
; : Less-than relation for keys
; inf : Infinity w.r.t. the inequality `>?'
; data : Vector data-store underlying heap
; size : Size of the heap as distinct from size of data
; membership : Mapping from data to indices
(define-record-and-printer heap >? inf data size membership)
=== {{heap-empty?}}
(heap-empty? heap) → boolean
Is the heap empty?
; heap : The heap to check
(define (heap-empty? heap) (zero? (heap-size heap)))
=== {{heap-member?}}
(heap-member? heap datum) → boolean
Is this datum a member in the heap?
; heap : The heap in which to check
; datum : The datum to check for
(define (heap-member? heap datum) (and (heap-index heap datum) #t))
=== {{heap-key}}
(heap-key heap datum) → unspecified
Find the key, given the datum.
; heap : The heap in which to search
; datum : The datum whose key to find
(define (heap-key heap datum)
(let ((index (heap-index heap datum)))
(and index (element-key (heap-ref heap index)))))
=== {{initial-heap-size}}
initial-heap-size → 100
Initial size of the heap data-store; exponentially resized on
overflow.
(define initial-heap-size (make-parameter 100))
=== {{make-max-heap}}
(make-max-heap) → max-heap
(make-max-heap initial-heap-size) → max-heap
Make a max-heap.
; size : Initial heap-size
(define make-max-heap
(case-lambda
(() (make-max-heap (initial-heap-size)))
((initial-heap-size)
(make-heap
>
<
-inf.0
(make-vector initial-heap-size)
0
(make-hash-table)))))
=== {{make-min-heap}}
(make-min-heap) → min-heap
(make-min-heap initial-heap-size) → min-heap
Make a min-heap.
; size : Initial heap-size
(define make-min-heap
(case-lambda
(() (make-min-heap (initial-heap-size)))
((initial-heap-size)
(make-heap
<
>
+inf.0
(make-vector initial-heap-size)
0
(make-hash-table)))))
=== {{heap-extremum}}
(heap-extremum heap) → datum
Peak at the heap's extremum (min or max).
; heap : The heap at which to peek
(define (heap-extremum heap)
(if (heap-empty? heap)
(error "Heap underflow -- HEAP-EXTREMUM")
(element-datum (heap-ref heap 0))))
=== {{heap-extract-extremum!}}
(heap-extract-extremum! heap) → datum
Return and delete the heap's extremum (min or max).
; heap : The heap from which to extract
(define (heap-extract-extremum! heap)
(let ((extremum (heap-extremum heap)))
(heap-set! heap 0 (heap-ref heap (- (heap-size heap) 1)))
(heap-size-set! heap (- (heap-size heap) 1))
(heapify!/index heap 0)
extremum))
=== {{heap-change-key!}}
(heap-change-key! heap datum new-key) → unspecified
Change the key of the element with datum to new-key along the
heap-gradient.
; heap : The heap in which to change
; datum : The datum whose key to change
; new-key : The new key to assign to element with datum
(define (heap-change-key! heap datum new-key)
(let ((i (heap-index heap datum)))
(if i
(heap-change-key!/index heap i new-key)
(error "Datum not found -- HEAP-CHANGE-KEY!"))))
=== {{heap-insert!}}
(heap-insert! heap key datum) → unspecified
Insert a new element into the heap if the datum does not exist;
otherwise, adjust its key.
; heap : The heap in which to insert
; element : The element to be inserted
(define (heap-insert! heap key datum)
(if (heap-member? heap datum)
(heap-change-key! heap datum key)
(let ((heap-size (heap-size heap)))
(if (= heap-size (heap-length heap))
(heap-data-set! heap (vector-resize (heap-data heap) (* 2 heap-size))))
(heap-size-set! heap (+ heap-size 1))
(let ((element (make-element (heap-inf heap) datum)))
(heap-set! heap heap-size element)
(heap-change-key!/index heap heap-size key)))))
=== {{heap-delete!}}
(heap-delete! heap datum) → unspecified
Delete the element with datum
; heap : The heap from which to delete
; datum : The datum whose element to delete
(define (heap-delete! heap datum)
(let ((i (heap-index heap datum)))
(if i
(heap-delete!/index heap i)
(error "Datum not found -- HEAP-DELETE!"))))
=== {{heap->list}}
(heap->list heap) → list
Convert the heap into a key-sorted list of values by iteratively
extracting the extremum; see also [[heap->alist]].
; heap : The heap to convert
(define (heap->list heap)
(let ((heap (heap-copy heap)))
(do ((list '() (cons (heap-extract-extremum! heap) list)))
((heap-empty? heap) list))))
=== {{heap->alist}}
(heap->alist heap) → alist
Convert the heap into a key-sorted list of key-value pairs by iteratively extracting the extremum; see also [[heap->list]].
; heap : The heap to convert
(define (heap->alist heap)
(let ((heap (heap-copy heap)))
(do ((list '()
(let ((datum (heap-extremum heap)))
(alist-cons
(heap-key heap datum)
(heap-extract-extremum! heap)
list))))
((heap-empty? heap) list))))
=== About this egg
==== Author
[[/users/klutometis|Peter Danenberg]]
==== Repository
[[https://github.com/klutometis/heap]]
==== License
BSD
==== Dependencies
* [[cock]]
* [[debug]]
* [[define-record-and-printer]]
* [[miscmacros]]
* [[vector-lib]]
==== Versions
; [[https://github.com/klutometis/heap/releases/tag/0.1|0.1]] : Initial version
; [[https://github.com/klutometis/heap/releases/tag/0.1.1|0.1.1]] : Add release-info.
; [[https://github.com/klutometis/heap/releases/tag/0.1.2|0.1.2]] : Add test.
; [[https://github.com/klutometis/heap/releases/tag/0.1.3|0.1.3]] : Update docs.
; [[https://github.com/klutometis/heap/releases/tag/0.2|0.2]] : Membership-testing
; [[https://github.com/klutometis/heap/releases/tag/0.2.2|0.2.2]] : Cleanup
; [[https://github.com/klutometis/heap/releases/tag/0.3|0.3]] : Enforce unique data.
; [[https://github.com/klutometis/heap/releases/tag/0.3.1|0.3.1]] : Fix make-min-heap.
; [[https://github.com/klutometis/heap/releases/tag/0.4|0.4]] : Simplified data-based API
; [[https://github.com/klutometis/heap/releases/tag/0.4.1|0.4.1]] : Remove phantom release.
; [[https://github.com/klutometis/heap/releases/tag/0.4.2|0.4.2]] : With a note about cock-utils
; [[https://github.com/klutometis/heap/releases/tag/0.4.3|0.4.3]] : Export heap-size.
; [[https://github.com/klutometis/heap/releases/tag/0.4.4|0.4.4]] : Proper infinities
; [[https://github.com/klutometis/heap/releases/tag/0.4.5|0.4.5]] : Add test-exit.
; [[https://github.com/klutometis/heap/releases/tag/0.4.6|0.4.6]] : Remove AIMA.
; [[https://github.com/klutometis/heap/releases/tag/0.4.7|0.4.7]] : Fix max heaps.
; [[https://github.com/klutometis/heap/releases/tag/0.4.8|0.4.8]] : Add an empty-heap guard on heap-extremum.
; [[https://github.com/klutometis/heap/releases/tag/0.4.9|0.4.9]] : heap->list, heap->alist
==== Colophon
Documented by [[/egg/cock|cock]].