Heap (historical revision 27517) - The CHICKEN Scheme wiki

You are looking at historical revision 27517 of this page. It may differ significantly from its current revision.

Heap

Mutable heap with priority-queue functions and O(1) membership-testing, which is useful for implementing e.g. A*

`heap`

[record] heap

The heap data-structure

>?: Greater-than relation for keys
=?: Equal-to relation for keys
inf: Infinity w.r.t. the inequality `>?'
key: Key-accessor for heap-elements
key-set!: Key-mutator for heap-elements
datum: Datum-accessor for heap-elements
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
  key
  key-set!
  datum
  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-index`

[procedure] (heap-index heap datum) → integer or #f

For a given datum, determine its index in the heap; or return #f

heap: The heap in which to check
datum: The datum to check for

(define (heap-index heap datum)
  (hash-table-ref/default (heap-membership heap) datum #f))

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

`heapify!/index`

[procedure] (heapify!/index heap i) → unspecified

Given a heap-index, reëstablish the heap-property.

heap: The heap in which to heapify
i: The element-index to heapify

(define (heapify!/index heap i)
  (let ((heap->? (heap->? heap)) (heap-key (heap-key heap)))
    (let ((left (left i)) (right (right i)))
      (let* ((extremum
               (if (and (< left (heap-size heap))
                        (heap->?
                          (heap-key (heap-ref heap left))
                          (heap-key (heap-ref heap i))))
                 left
                 i))
             (extremum
               (if (and (< right (heap-size heap))
                        (heap->?
                          (heap-key (heap-ref heap right))
                          (heap-key (heap-ref heap extremum))))
                 right
                 extremum)))
        (if (not (= extremum i))
          (begin
            (heap-swap! heap i extremum)
            (heapify!/index heap extremum)))))))

`heapify!`

[procedure] (heapify! heap datum) → unspecified

Given a heap-index, reëstablish the heap-property.

heap: The heap in which to heapify
datum: The datum whose element to heapify

(define (heapify! heap datum)
  (let ((i (heap-index heap datum)))
    (if i (heapify! heap i) (error "Datum not found -- HEAPIFY!"))))

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

[procedure] (make-max-heap) → max-heap
[procedure] (make-max-heap key key-set! datum) → max-heap
[procedure] (make-max-heap key key-set! datum data) → max-heap
[procedure] (make-max-heap key key-set! datum data size) → max-heap

Make a max-heap.

key: Key-accessor for heap-elements
key-set!: Key-mutator for heap-elements
datum: Datum-accessor for heap-elements
data: Vector data-store underlying heap
size: Size of the heap as distinct from size of data

(define make-max-heap
  (case-lambda
    (() (make-max-heap car set-car! cdr))
    ((key key-set! datum)
     (make-max-heap key key-set! datum (make-vector (initial-heap-size)) 0))
    ((key key-set! datum data)
     (make-max-heap key key-set! datum data (vector-length data)))
    ((key key-set! datum data size)
     (make-heap > = -inf key key-set! datum data size (make-hash-table)))))

`make-min-heap`

[procedure] (make-min-heap) → min-heap
[procedure] (make-min-heap key key-set! datum) → min-heap
[procedure] (make-min-heap key key-set! datum data) → min-heap
[procedure] (make-min-heap key key-set! datum data size) → min-heap

Make a min-heap.

key: Key-accessor for heap-elements
key-set!: Key-mutator for heap-elements
datum: Datum-accessor for heap-elements
data: Vector data-store underlying heap
size: Size of the heap as distinct from size of data

(define make-min-heap
  (case-lambda
    (() (make-max-heap car set-car! cdr))
    ((key key-set! datum)
     (make-max-heap key key-set! datum (make-vector (initial-heap-size)) 0))
    ((key key-set! datum data)
     (make-max-heap key key-set! datum data (vector-length data)))
    ((key key-set! datum data size)
     (make-heap < = +inf key key-set! datum data size (make-hash-table)))))

`build-heap!`

[procedure] (build-heap! heap) → unspecified

Heapify the entire data-store.

heap: The heap to heapify

(define (build-heap! heap)
  (heap-size-set! heap (vector-length (heap-data heap)))
  (let ((median (inexact->exact (floor (/ (heap-size heap) 2)))))
    (do ((i (sub1 median) (sub1 i))) ((negative? i)) (heapify!/index heap i))))

`heap-extremum`

[procedure] (heap-extremum heap) → extreme element

Peak at the heap's extremum (min or max).

heap: The heap at which to peek

(define (heap-extremum heap) (heap-ref heap 0))

`heap-extract-extremum!`

[procedure] (heap-extract-extremum! heap) → extreme element

Return and delete the heap's extremum (min or max).

heap: The heap from which to extract

(define (heap-extract-extremum! heap)
  (if (zero? (heap-size heap))
    (error "Heap underflow -- HEAP-EXTRACT-EXTREMUM!")
    (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!/index`

[procedure] (heap-change-key!/index heap i new-key) → unspecified

Change the key of the ith element to new-key along the heap-gradient.

heap: The heap in which to change
i: The index of the element whose key to change
new-key: The new key to assign to element i

(define (heap-change-key!/index heap i new-key)
  (let ((heap->? (heap->? heap))
        (heap-=? (heap-=? heap))
        (heap-key (heap-key heap)))
    (let ((old-key (heap-key (heap-ref heap i))))
      (if (or (heap->? new-key old-key) (heap-=? new-key old-key))
        (begin
          ((heap-key-set! heap) (heap-ref heap i) new-key)
          (do ((i i (parent i)))
              ((or (zero? i)
                   (heap->?
                     (heap-key (heap-ref heap (parent i)))
                     (heap-key (heap-ref heap i)))))
            (heap-swap! heap i (parent i))))
        (error "Key violates heap-gradient -- HEAP-CHANGE-KEY!")))))

`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 element) → 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 element)
  (let ((key ((heap-key heap) element)) (datum ((heap-datum heap) element)))
    (if (heap-member? heap datum)
      (heap-change-key! heap key datum)
      (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 ((key ((heap-key heap) element)))
          ((heap-key-set! heap) element (heap-inf heap))
          (heap-set! heap heap-size element)
          (heap-change-key!/index heap heap-size key))))))

`heap-delete!/index`

[procedure] (heap-delete!/index heap i) → unspecified

Delete the ith element from the heap

heap: The heap from which to delete
i: The index of the element to delete

(define (heap-delete!/index heap i)
  (let ((heap-size (- (heap-size heap) 1)))
    (if (negative? heap-size)
      (error "Heap underflow -- HEAP-DELETE!")
      (let ((datum ((heap-datum heap) (heap-ref heap i))))
        (hash-table-delete! (heap-membership heap) datum)
        (heap-size-set! heap heap-size)
        (heap-set! heap i (heap-ref heap heap-size))
        (heapify!/index heap i)))))

`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!"))))