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

`heap`- The heap to check

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

heap-member?

`heap-member?``heap``datum`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`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`parameterInitial size of the heap data-store; exponentially resized on overflow.

(define initial-heap-size (make-parameter 100))

make-max-heap

`make-max-heap`procedure`make-max-heap``initial-heap-size`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`procedure`make-min-heap``initial-heap-size`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`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`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`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`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`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`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`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.