heap

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

  1. heap
    1. heap
    2. heap-empty?
    3. heap-member?
    4. heap-key
    5. initial-heap-size
    6. make-max-heap
    7. make-min-heap
    8. heap-extremum
    9. heap-extract-extremum!
    10. heap-change-key!
    11. heap-insert!
    12. heap-delete!
    13. heap->list
    14. heap->alist
    15. About this egg
      1. Author
      2. Repository
      3. License
      4. Dependencies
      5. Versions
      6. Colophon

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

About this egg

Author

Peter Danenberg

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.