(index ("heap" 0) ("heap-empty?" 508) ("heap-member?" 728) ("heap-key" 1045) ("initial-heap-size" 1418) ("make-max-heap" 1640) ("make-max-heap" 1640) ("make-min-heap" 2127) ("make-min-heap" 2127) ("heap-extremum" 2614) ("heap-extract-extremum!" 2959) ("heap-change-key!" 3430) ("heap-insert!" 4019) ("heap-delete!" 4821) ("heap->list" 5254) ("heap->alist" 5690))
(def (sig (record "heap" (id heap))) (p "The heap data-structure") (dl (dt (tt ">?")) (dd "Greater-than relation for keys") (dt (tt "<?")) (dd "Less-than relation for keys") (dt (tt "inf")) (dd "Infinity w.r.t. the inequality `>?'") (dt (tt "data")) (dd "Vector data-store underlying heap") (dt (tt "size")) (dd "Size of the heap as distinct from size of data") (dt (tt "membership")) (dd "Mapping from data to indices")) (highlight scheme "(define-record-and-printer heap >? <? inf data size membership)"))
(def (sig (procedure "(heap-empty? heap) → boolean" (id heap-empty?))) (p "Is the heap empty?") (dl (dt (tt "heap")) (dd "The heap to check")) (highlight scheme "(define (heap-empty? heap) (zero? (heap-size heap)))"))
(def (sig (procedure "(heap-member? heap datum) → boolean" (id heap-member?))) (p "Is this datum a member in the heap?") (dl (dt (tt "heap")) (dd "The heap in which to check") (dt (tt "datum")) (dd "The datum to check for")) (highlight scheme "(define (heap-member? heap datum) (and (heap-index heap datum) #t))"))
(def (sig (procedure "(heap-key heap datum) → unspecified" (id heap-key))) (p "Find the key, given the datum.") (dl (dt (tt "heap")) (dd "The heap in which to search") (dt (tt "datum")) (dd "The datum whose key to find")) (highlight scheme "(define (heap-key heap datum)\n  (let ((index (heap-index heap datum)))\n    (and index (element-key (heap-ref heap index)))))"))
(def (sig (parameter "initial-heap-size → 100" (id initial-heap-size))) (p "Initial size of the heap data-store; exponentially resized on overflow.") (highlight scheme "(define initial-heap-size (make-parameter 100))"))
(def (sig (procedure "(make-max-heap) → max-heap" (id make-max-heap)) (procedure "(make-max-heap initial-heap-size) → max-heap" (id make-max-heap))) (p "Make a max-heap.") (dl (dt (tt "size")) (dd "Initial heap-size")) (highlight scheme "(define make-max-heap\n  (case-lambda\n    (() (make-max-heap (initial-heap-size)))\n    ((initial-heap-size)\n     (make-heap\n       >\n       <\n       -inf.0\n       (make-vector initial-heap-size)\n       0\n       (make-hash-table)))))"))
(def (sig (procedure "(make-min-heap) → min-heap" (id make-min-heap)) (procedure "(make-min-heap initial-heap-size) → min-heap" (id make-min-heap))) (p "Make a min-heap.") (dl (dt (tt "size")) (dd "Initial heap-size")) (highlight scheme "(define make-min-heap\n  (case-lambda\n    (() (make-min-heap (initial-heap-size)))\n    ((initial-heap-size)\n     (make-heap\n       <\n       >\n       +inf.0\n       (make-vector initial-heap-size)\n       0\n       (make-hash-table)))))"))
(def (sig (procedure "(heap-extremum heap) → datum" (id heap-extremum))) (p "Peak at the heap's extremum (min or max).") (dl (dt (tt "heap")) (dd "The heap at which to peek")) (highlight scheme "(define (heap-extremum heap)\n  (if (heap-empty? heap)\n    (error \"Heap underflow -- HEAP-EXTREMUM\")\n    (element-datum (heap-ref heap 0))))"))
(def (sig (procedure "(heap-extract-extremum! heap) → datum" (id heap-extract-extremum!))) (p "Return and delete the heap's extremum (min or max).") (dl (dt (tt "heap")) (dd "The heap from which to extract")) (highlight scheme "(define (heap-extract-extremum! heap)\n  (let ((extremum (heap-extremum heap)))\n    (heap-set! heap 0 (heap-ref heap (- (heap-size heap) 1)))\n    (heap-size-set! heap (- (heap-size heap) 1))\n    (heapify!/index heap 0)\n    extremum))"))
(def (sig (procedure "(heap-change-key! heap datum new-key) → unspecified" (id heap-change-key!))) (p "Change the key of the element with datum to new-key along the heap-gradient.") (dl (dt (tt "heap")) (dd "The heap in which to change") (dt (tt "datum")) (dd "The datum whose key to change") (dt (tt "new-key")) (dd "The new key to assign to element with datum")) (highlight scheme "(define (heap-change-key! heap datum new-key)\n  (let ((i (heap-index heap datum)))\n    (if i\n      (heap-change-key!/index heap i new-key)\n      (error \"Datum not found -- HEAP-CHANGE-KEY!\"))))"))
(def (sig (procedure "(heap-insert! heap key datum) → unspecified" (id heap-insert!))) (p "Insert a new element into the heap if the datum does not exist; otherwise, adjust its key.") (dl (dt (tt "heap")) (dd "The heap in which to insert") (dt (tt "element")) (dd "The element to be inserted")) (highlight scheme "(define (heap-insert! heap key datum)\n  (if (heap-member? heap datum)\n    (heap-change-key! heap datum key)\n    (let ((heap-size (heap-size heap)))\n      (if (= heap-size (heap-length heap))\n        (heap-data-set! heap (vector-resize (heap-data heap) (* 2 heap-size))))\n      (heap-size-set! heap (+ heap-size 1))\n      (let ((element (make-element (heap-inf heap) datum)))\n        (heap-set! heap heap-size element)\n        (heap-change-key!/index heap heap-size key)))))"))
(def (sig (procedure "(heap-delete! heap datum) → unspecified" (id heap-delete!))) (p "Delete the element with datum") (dl (dt (tt "heap")) (dd "The heap from which to delete") (dt (tt "datum")) (dd "The datum whose element to delete")) (highlight scheme "(define (heap-delete! heap datum)\n  (let ((i (heap-index heap datum)))\n    (if i\n      (heap-delete!/index heap i)\n      (error \"Datum not found -- HEAP-DELETE!\"))))"))
(def (sig (procedure "(heap->list heap) → list" (id heap->list))) (p "Convert the heap into a key-sorted list of values by iteratively extracting the extremum; see also " (int-link "heap->alist") ".") (dl (dt (tt "heap")) (dd "The heap to convert")) (highlight scheme "(define (heap->list heap)\n  (let ((heap (heap-copy heap)))\n    (do ((list '() (cons (heap-extract-extremum! heap) list)))\n        ((heap-empty? heap) list))))"))
(def (sig (procedure "(heap->alist heap) → alist" (id heap->alist))) (p "Convert the heap into a key-sorted list of key-value pairs by iteratively extracting the extremum; see also " (int-link "heap->list") ".") (dl (dt (tt "heap")) (dd "The heap to convert")) (highlight scheme "(define (heap->alist heap)\n  (let ((heap (heap-copy heap)))\n    (do ((list '()\n               (let ((datum (heap-extremum heap)))\n                 (alist-cons\n                   (heap-key heap datum)\n                   (heap-extract-extremum! heap)\n                   list))))\n        ((heap-empty? heap) list))))"))
