You are looking at historical revision 28549 of this page. It may differ significantly from its current revision.
title
Mutable heap with priority-queue functions and O(1) membership-testing, which is useful for implementing e.g. A*
heap
[record] heapThe 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?
[procedure] (heap-empty? heap) → booleanIs the heap empty?
- heap
- The heap to check
(define (heap-empty? heap) (zero? (heap-size heap)))
heap-member?
[procedure] (heap-member? heap datum) → booleanIs 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
[procedure] (heap-key heap datum) → unspecifiedFind 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
[parameter] initial-heap-size → 100Initial size of the heap data-store; exponentially resized on overflow.
(define initial-heap-size (make-parameter 100))
make-max-heap
[procedure] (make-max-heap) → max-heap[procedure] (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
(make-vector initial-heap-size)
0
(make-hash-table)))))
make-min-heap
[procedure] (make-min-heap) → min-heap[procedure] (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
(make-vector initial-heap-size)
0
(make-hash-table)))))
heap-extremum
[procedure] (heap-extremum heap) → datumPeak at the heap's extremum (min or max).
- heap
- The heap at which to peek
(define (heap-extremum heap) (element-datum (heap-ref heap 0)))
heap-extract-extremum!
[procedure] (heap-extract-extremum! heap) → datumReturn and delete the heap's extremum (min or max).
- heap
- The heap from which to extract
(define (heap-extract-extremum! heap)
(if (zero? (heap-size heap))
(error "Heap underflow -- HEAP-EXTRACT-EXTREMUM!")
(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!
[procedure] (heap-change-key! heap datum new-key) → unspecifiedChange 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!
[procedure] (heap-insert! heap key datum) → unspecifiedInsert 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!
[procedure] (heap-delete! heap datum) → unspecifiedDelete 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
[procedure] (heap->list heap) → listConvert 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
[procedure] (heap->alist heap) → alistConvert 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
Colophon
Documented by cock.