module Heap: sig .. end
Simple implementation of an array-based binary heap in OCaml.
Automatically resizes when attempting to add to a full array.
Click
here for the pseudo-code.
type 'a heap = 'a Heap.heap = {
|
mutable data : 'a array; |
|
mutable size : int; |
|
lessthan : 'a -> 'a -> bool; |
}
val create : ('a -> 'a -> bool) -> int -> 'a heap
create lessthan n creates a heap with the capacity n and
the comparison function lessthan.
val realloc : 'a heap -> int -> unit
realloc h n grows the capacity of the heap h to n.
val size : 'a heap -> int
size h returns the number of items in the heap h.
val is_empty : 'a heap -> bool
is_empty h checks if the heap h is empty.
val grow : 'a heap -> unit
grow h automatically resizes the size of the heap h.
val swap : 'a heap -> int -> int -> unit
swap h x y swaps two items x and y in the heap h.
val sift_down : 'a heap -> int -> unit
sift_down h root moves root down to satisfy the heap
property for the heap h.
val sift_up : 'a heap -> int -> unit
sift_up h child moves child up to satisfy the heap
property for the heap h.
val add : 'a heap -> 'a -> unit
add h x adds the element x to the heap h, growing if
necessary.
val remove_min : 'a heap -> unit
remove_min h removes the smallest element in heap h (root).
val get : 'a heap -> int -> 'a
get h i gets the ith element in the heap h.
val remove : 'a heap -> int -> unit
remove h i removes the ith element in the heap h.
val min : 'a heap -> 'a
min h accesses the smallest element in the heap h.
val rebuild : 'a heap -> unit
rebuild h fixes all out-of-order elements in the heap h in
linear time.
val build : ('a -> 'a -> bool) -> 'a array -> 'a heap
build lessthan a builds a heap from the existing array a
with respect to the comparison function lessthan.
Runs in O(n) time.
val remove_all : 'a heap -> ('a -> bool) -> unit
remove_all h f removes all elements from the heap h that
match the criterion f. Runs in O(n) time.
val clear : 'a heap -> unit
clear h removes all elements from the heap h.
val iter : ('a -> 'b) -> 'a heap -> unit
iter f h applies the function f over the elements of the
heap h.
val to_array : 'a heap -> 'a array
to_array h constructs an array from the elements of the heap h.
val to_list : 'a heap -> 'a list
to_list h constructs a list from the elements of the heap h.