▼Data:   Data Structures
On this page:
make-heap
heap?
heap-count
heap-add!
heap-add-all!
heap-min
heap-remove-min!
heap-remove!
vector->heap
heap->vector
heap-copy
in-heap/  consume!
in-heap
heap-sort!
6.2
  top  ← prev  up  next → 

7 Binary Heaps

Ryan Culpepper <ryanc@racket-lang.org>

 (require data/heap) package: data-lib

Binary heaps are a simple implementation of priority queues.

Operations on binary heaps are not thread-safe.

procedure

(make-heap <=?) → heap?

  <=? : (-> any/c any/c any/c)
Makes a new empty heap using <=? to order elements.

Examples:

> (define a-heap-of-strings (make-heap string<=?))
> a-heap-of-strings

#<heap>

; With structs:
> (struct node (name val))
> (define (node<=? x y)
    (<= (node-val x) (node-val y)))
> (define a-heap-of-nodes (make-heap node<=?))
> a-heap-of-nodes

#<heap>

procedure

(heap? x) → boolean?

  x : any/c
Returns #t if x is a heap, #f otherwise.

Examples:

> (heap? (make-heap <=))

#t

> (heap? "I am not a heap")

#f

procedure

(heap-count h) → exact-nonnegative-integer?

  h : heap?
Returns the number of elements in the heap.

Examples:

> (define a-heap (make-heap <=))
> (heap-add-all! a-heap '(7 3 9 1 13 21 15 31))
> (heap-count a-heap)

8

procedure

(heap-add! h v ...) → void?

  h : heap?
  v : any/c
Adds each v to the heap.

Examples:

> (define a-heap (make-heap <=))
> (heap-add! a-heap 2009 1009)

procedure

(heap-add-all! h v) → void?

  h : heap?
  v : (or/c list? vector? heap?)
Adds each element contained in v to the heap, leaving v unchanged.

Examples:

> (define heap-1 (make-heap <=))
> (define heap-2 (make-heap <=))
> (define heap-12 (make-heap <=))
> (heap-add-all! heap-1 '(3 1 4 1 5 9 2 6))
> (heap-add-all! heap-2 #(2 7 1 8 2 8 1 8))
> (heap-add-all! heap-12 heap-1)
> (heap-add-all! heap-12 heap-2)
> (heap-count heap-12)

16

procedure

(heap-min h) → any/c

  h : heap?
Returns the least element in the heap h, according to the heap’s ordering. If the heap is empty, an exception is raised.

Examples:

> (define a-heap (make-heap string<=?))
> (heap-add! a-heap "sneezy" "sleepy" "dopey" "doc"
             "happy" "bashful" "grumpy")
> (heap-min a-heap)

"bashful"

; Taking the min of the empty heap is an error:
> (heap-min (make-heap <=))

heap-min: empty heap

procedure

(heap-remove-min! h) → void?

  h : heap?
Removes the least element in the heap h. If the heap is empty, an exception is raised.

Examples:

> (define a-heap (make-heap string<=?))
> (heap-add! a-heap "fili" "fili" "oin" "gloin" "thorin"
                    "dwalin" "balin" "bifur" "bofur"
                    "bombur" "dori" "nori" "ori")
> (heap-min a-heap)

"balin"

> (heap-remove-min! a-heap)
> (heap-min a-heap)

"bifur"

procedure

(heap-remove! h v [#:same? same?]) → void?

  h : heap?
  v : any/c
  same? : (-> any/c any/c any/c) = equal?
Removes v from the heap h if it exists.

Examples:

> (define a-heap (make-heap string<=? string=?))

make-heap: arity mismatch;

 the expected number of arguments does not match the given

number

  expected: 1

  given: 2

  arguments...:

   #<procedure:string<=?>

   #<procedure:string=?>

> (heap-add! a-heap "a" "b" "c")
> (heap-remove! a-heap "b")
> (for/list ([a (in-heap a-heap)]) a)

'("a"

  "bifur"

  "bofur"

  "bombur"

  "c"

  "dori"

  "dwalin"

  "fili"

  "fili"

  "gloin"

  "nori"

  "oin"

  "ori"

  "thorin")

procedure

(vector->heap <=? items) → heap?

  <=? : (-> any/c any/c any/c)
  items : vector?
Builds a heap with the elements from items. The vector is not modified.

Examples:

> (struct item (val frequency))
> (define (item<=? x y)
    (<= (item-frequency x) (item-frequency y)))
> (define some-sample-items
    (vector (item #\a 17) (item #\b 12) (item #\c 19)))
> (define a-heap (vector->heap item<=? some-sample-items))

procedure

(heap->vector h) → vector?

  h : heap?
Returns a vector containing the elements of heap h in the heap’s order. The heap is not modified.

Examples:

> (define word-heap (make-heap string<=?))
> (heap-add! word-heap "pile" "mound" "agglomerate" "cumulation")
> (heap->vector word-heap)

'#("agglomerate" "cumulation" "mound" "pile")

procedure

(heap-copy h) → heap?

  h : heap?
Makes a copy of heap h.

Examples:

> (define word-heap (make-heap string<=?))
> (heap-add! word-heap "pile" "mound" "agglomerate" "cumulation")
> (define a-copy (heap-copy word-heap))
> (heap-remove-min! a-copy)
> (heap-count word-heap)

4

> (heap-count a-copy)

3

procedure

(in-heap/consume! heap) → sequence?

  heap : heap?
Returns a sequence equivalent to heap, maintaining the heap’s ordering. The heap is consumed in the process. Equivalent to repeated calling heap-min, then heap-remove-min!.

Examples:

> (define h (make-heap <=))
> (heap-add-all! h '(50 40 10 20 30))
> (for ([x (in-heap/consume! h)])
    (displayln x))

10

20

30

40

50

> (heap-count h)

0

procedure

(in-heap heap) → sequence?

  heap : heap?
Returns a sequence equivalent to heap, maintaining the heap’s ordering. Equivalent to in-heap/consume! except the heap is copied first.

Examples:

> (define h (make-heap <=))
> (heap-add-all! h '(50 40 10 20 30))
> (for ([x (in-heap h)])
    (displayln x))

10

20

30

40

50

> (heap-count h)

5

procedure

(heap-sort! v <=?) → void?

  v : (and/c vector? (not/c immutable?))
  <=? : (-> any/c any/c any/c)
Sorts vector v using the comparison function <=?.

Examples:

> (define terms (vector "batch" "deal" "flock" "good deal" "hatful" "lot"))
> (heap-sort! terms string<=?)
> terms

'#("batch" "deal" "flock" "good deal" "hatful" "lot")

  top  ← prev  up  next →