## 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-printerheap >? <? 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.

(defineinitial-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

(definemake-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

(definemake-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))) (ifi (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))) (ifi (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))))

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

#### Colophon

Documented by cock.