## heap

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

## TOC »

`heap`

`heap`recordThe 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`procedureIs the heap empty?

`heap`- The heap to check

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

`heap-member?`

`(heap-member? heap datum) → boolean`procedureIs 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`procedureFind 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`parameterInitial 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`procedure`(make-max-heap initial-heap-size) → max-heap`procedureMake 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`procedure`(make-min-heap initial-heap-size) → min-heap`procedureMake 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`procedurePeak 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`procedureReturn 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`procedureChange 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`procedureInsert 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`procedureDelete 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`procedureConvert 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`procedureConvert 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

#### Repository

https://github.com/klutometis/heap

#### License

BSD

#### Dependencies

#### Versions

- 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.