You are looking at historical revision 27487 of this page. It may differ significantly from its current revision.
Heap
Mutable heap with O(1) membership-testing
heap
[module] heap
The heap module provides basic priority queue functions with O(1) membership-testing, which is useful for implementing e.g. A*.
- build-heap!
- heap-data
- initial-heap-size
- make-heap
- make-max-heap
- make-min-heap
- heap-change-key!
- heap-delete!
- heap-empty?
- heap-extract-extremum!
- heap-extremum
- heap-insert!
- heapify!
heap
[record] heapThe heap data-structure
- >?
- Greater-than relation for keys
- =?
- Equal-to relation for keys
- inf
- Infinity w.r.t. the inequality `>?'
- key
- Key-accessor for heap-elements
- key-set!
- Key-mutator for heap-elements
- data
- Vector data-store underlying heap
- size
- Size of the heap as distinct from size of data
(define-record-and-printer heap >? =? inf key key-set! data size)
heap-empty?
[procedure] (heap-empty? heap) → booleanIs the heap empty?
- heap
- The heap to check
(define (heap-empty? heap) (zero? (heap-size heap)))
heapify!
[procedure] (heapify! heap i) → unspecifiedGiven a heap-index, reëstablish the heap-property.
- heap
- The heap in which to heapify
- i
- The element-index to heapify
(define (heapify! heap i)
(let ((heap->? (heap->? heap)) (heap-key (heap-key heap)))
(let ((left (left i)) (right (right i)))
(let* ((extremum
(if (and (< left (heap-size heap))
(heap->?
(heap-key (heap-ref heap left))
(heap-key (heap-ref heap i))))
left
i))
(extremum
(if (and (< right (heap-size heap))
(heap->?
(heap-key (heap-ref heap right))
(heap-key (heap-ref heap extremum))))
right
extremum)))
(if (not (= extremum i))
(begin (heap-swap! heap i extremum) (heapify! heap extremum)))))))
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 key key-set!) → max-heap
[procedure] (make-max-heap key key-set! data) → max-heap
[procedure] (make-max-heap key key-set! data size) → max-heap
Make a max-heap.
- key
- Key-accessor for heap-elements
- key-set!
- Key-mutator for heap-elements
- data
- Vector data-store underlying heap
- size
- Size of the heap as distinct from size of data
(define make-max-heap
(case-lambda
(() (make-max-heap car set-car!))
((key key-set!)
(make-max-heap key key-set! (make-vector (initial-heap-size)) 0))
((key key-set! data)
(make-max-heap key key-set! data (vector-length data)))
((key key-set! data size) (make-heap > = -inf key key-set! data size))))
make-min-heap
[procedure] (make-min-heap) → min-heap[procedure] (make-min-heap key key-set!) → min-heap
[procedure] (make-min-heap key key-set! data) → min-heap
[procedure] (make-min-heap key key-set! data size) → min-heap
Make a min-heap.
- key
- Key-accessor for heap-elements
- key-set!
- Key-mutator for heap-elements
- data
- Vector data-store underlying heap
- size
- Size of the heap as distinct from size of data
(define make-min-heap
(case-lambda
(() (make-max-heap car set-car!))
((key key-set!)
(make-max-heap key key-set! (make-vector (initial-heap-size)) 0))
((key key-set! data)
(make-max-heap key key-set! data (vector-length data)))
((key key-set! data size) (make-heap < = +inf key key-set! data size))))
build-heap!
[procedure] (build-heap! heap) → unspecifiedHeapify the entire data-store.
- heap
- The heap to heapify
(define (build-heap! heap)
(heap-size-set! heap (vector-length (heap-data heap)))
(let ((median (inexact->exact (floor (/ (heap-size heap) 2)))))
(do ((i (sub1 median) (sub1 i))) ((negative? i)) (heapify! heap i))))
heap-extremum
[procedure] (heap-extremum heap) → extreme elementPeak at the heap's extremum (min or max).
- heap
- The heap at which to peek
(define (heap-extremum heap) (heap-ref heap 0))
heap-extract-extremum!
[procedure] (heap-extract-extremum! heap) → extreme elementReturn 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! heap 0)
extremum)))
heap-change-key!
[procedure] (heap-change-key! heap i new-key) → unspecifiedChange the key of the ith element to new-key along the heap-gradient.
- heap
- The heap in which to change
- i
- The index of the element whose key to change
- new-key
- The new key to assign to element i
(define (heap-change-key! heap i new-key)
(let ((heap->? (heap->? heap))
(heap-=? (heap-=? heap))
(heap-key (heap-key heap)))
(let ((old-key (heap-key (heap-ref heap i))))
(if (or (heap->? new-key old-key) (heap-=? new-key old-key))
(begin
((heap-key-set! heap) (heap-ref heap i) new-key)
(do ((i i (parent i)))
((or (zero? i)
(heap->?
(heap-key (heap-ref heap (parent i)))
(heap-key (heap-ref heap i)))))
(heap-swap! heap i (parent i))))
(error "Key violates heap-gradient -- HEAP-CHANGE-KEY!")))))
heap-insert!
[procedure] (heap-insert! heap element) → unspecifiedInsert a new element into the heap.
- heap
- The heap in which to insert
- element
- The element to be inserted
(define (heap-insert! heap element)
(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 ((key ((heap-key heap) element)))
((heap-key-set! heap) element (heap-inf heap))
(heap-set! heap heap-size element)
(heap-change-key! heap heap-size key))))
heap-delete!
[procedure] (heap-delete! heap i) → unspecifiedDelete the ith element from the heap
- heap
- The heap from which to delete
- i
- The index of the element to delete
(define (heap-delete! heap i)
(let ((heap-size (- (heap-size heap) 1)))
(if (negative? heap-size)
(error "Heap underflow -- HEAP-DELETE!")
(begin
(heap-size-set! heap heap-size)
(heap-set! heap i (heap-ref heap heap-size))
(heapify! heap i)))))
About this egg
Author
Colophon
Documented by cock.