▼ |  | Data: Data Structures

1 | Imperative Queues
2 | Growable Vectors
3 | Orders and Ordered Dictionaries
4 | Splay Trees
5 | Skip Lists
6 | Interval Maps
7 | Binary Heaps

On this page:

make-heap
heap?
heap-count
heap-add!
heap-add-all!
heap-min
heap-remove-min!
vector->heap
heap->vector
heap-copy
heap-sort!

Version: 5.3
top← prev up next →

### 7`` Binary Heaps

Ryan Culpepper <ryanc@racket-lang.org>

(require data/heap)

Binary heaps are a simple implementation of priority queues.

> > procedure

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

> <=? : (-> any/c any/c any/c)

Makes a new empty heap using <=? to order elements.

> > procedure

> > (heap? x) → boolean?

> x : any/c

Returns #t if x is a heap, #f otherwise.

> > procedure

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

> h : heap?

Returns the number of elements in the heap.

> > procedure

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

> h : heap?
> v : any/c

Adds each v to the heap.

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

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

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

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

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

> > procedure

> > (heap-copy h) → heap?

> h : heap?

Makes a copy of heap h.

> > procedure

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

> <=? : (-> any/c any/c any/c)
> v : vector?

Sorts vector v using the comparison function <=?.
top← prev up next →