Outdated egg! (historical revision 39572)

You are looking at historical revision 39572 of this page. It may differ significantly from its current revision.

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

heap

Mutable heap with priority-queue operations and O(1) membership-testing

`heap`

[record] 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?`

[procedure] (heap-empty? heap) → boolean

Is the heap empty?

heap: The heap to check

(define (heap-empty? heap) (zero? (heap-size heap)))

`heap-member?`

[procedure] (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`

[procedure] (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`

[parameter] 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`

[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.0
       (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.0
       (make-vector initial-heap-size)
       0
       (make-hash-table)))))

`heap-extremum`

[procedure] (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!`

[procedure] (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!`

[procedure] (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!`

[procedure] (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!`

[procedure] (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`

[procedure] (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`

[procedure] (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))))

0.1: Initial version
0.1.1: Add release-info.
0.1.2: Add test.
0.1.3: Update docs.
0.2: Membership-testing
0.2.2: Cleanup
0.3: Enforce unique data.
0.3.1: Fix make-min-heap.
0.4: Simplified data-based API
0.4.1: Remove phantom release.
0.4.2: With a note about cock-utils
0.4.3: Export heap-size.
0.4.4: Proper infinities
0.4.5: Add test-exit.
0.4.6: Remove AIMA.
0.4.7: Fix max heaps.
0.4.8: Add an empty-heap guard on heap-extremum.
0.4.9: heap->list, heap->alist
0.4.10: Remove the dependency on setup-helper-cock.
0.4.11: Remove debug.
0.4.12: Use hahn.

Colophon

Documented by hahn.