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

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

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

Peter Danenberg

#### Repository

https://github.com/klutometis/heap

BSD

#### Versions

0.1
Initial version
0.1.1
0.1.2
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
0.4.3
Export heap-size.
0.4.4
Proper infinities
0.4.5
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.