Fibonacci Heap

Jay McCarthy <jay at plt-scheme dot org>

(require (planet jaymccarthy/fib-heap:1:0))

This package provides an imperative Fibonacci heap implementation based on this implementation.

(make-fib-heap <) → fib-heap?

< : (any/c any/c . -> . boolean?)

Constructs a heap that uses < to compare elements.

(fib-heap-size fh) → exact-nonnegative-integer?

fh : fib-heap?

Returns the number of elements in fh.

(fib-heap-extract-min! fh) → (or/c any/c false/c)

fh : fib-heap?

Extracts the minimum element from fh or returns #f if (zero? (fib-heap-size fh)).

(fib-heap-insert! fh v) → void

fh : fib-heap?

v : any/c

Inserts v into fh.

(fib-heap-union! fh1 fh2) → void

fh1 : fib-heap?

fh2 : fib-heap?

Efficiently inserts all the elements of fh2 into fh1.

(fib-heap-map! fh f) → (listof any/c)

fh : fib-heap?

f : (any/c . -> . any/c)

Returns a list that contains the result of calling f on each element of fh in the minimum order.

(fib-heap-for-each! fh f) → void

fh : fib-heap?

f : (any/c . -> . void)

Calls f on each element of fh in the minimum order. (Note: This might go into an infinite loop if f calls fib-heap-insert!)