Previous  Up  Next

Module Heap

module Heap: sig .. end
Min-heap implementation, adapted from CLR.

Exceptions

exception Empty
Raised when top or pop is called on an empty heap.

Types

type 'el t
Type of heaps
include Container.S1
type 'el heap_el
Type of heap elements (they can be efficiently removed)

Functions on heap elements

val heap_el_is_valid : 'el heap_el -> bool
heap_el_is_valid heap_el
Returns true iff heap element is member of a heap.
val heap_el_get_el : 'el heap_el -> 'el
heap_el_get_el heap_el
Returns the element associated with the heap element.
val heap_el_get_heap_exn : 'el heap_el -> 'el t
heap_el_get_heap_exn heap_el
Raises Failure if the element is not contained by some heap
Returns the heap that contains the element

Information on heap values

val get_cmp : 'el t -> 'el -> 'el -> int
get_cmp heap
Returns the ordering function used by heap.

Heap creation

val create : ?min_size:int -> ('el -> 'el -> int) -> 'el t
create ?min_size cmp
Returns a fresh heap that can store min_size elements without reallocations, using ordering function cmp.

If cmp x y < 0 (i.e. x < y), then x will be on "top" of y in the heap. That is, Heap.pop will remove x before y.

val of_array : ?min_size:int -> ('el -> 'el -> int) -> 'el array -> 'el t
of_array ?min_size cmp ar
Returns a fresh heap that can store min_size elements without reallocations, using ordering function cmp, and initialize it with the elements of ar.
val copy : 'el t -> 'el t
copy heap
Returns a copy of heap.

Search functions

val mem : 'el t -> 'el -> bool
mem heap el
Returns true iff el is member of heap. Requires linear time in worst case.
val heap_el_mem : 'el t -> 'el heap_el -> bool
heap_el_mem heap heap_el
Returns true iff heap_el is member of heap. Requires constant time only.
val find_heap_el_exn : 'el t -> 'el -> 'el heap_el
find_heap_el_exn heap el
Raises Not_found if el could not be found.
Returns the heap element associated with element el in heap.

Non-destructive heap accessors

val top : 'el t -> 'el option
top heap
Returns Some top_element of heap without changing it, or None if heap is empty.
val top_exn : 'el t -> 'el
top_exn heap
Raises Empty if heap is empty.
Returns the top element of heap without changing it.
val top_heap_el : 'el t -> 'el heap_el option
top_heap_el heap
Returns Some top_heap_el of heap without changing it, or None if heap is empty.
val top_heap_el_exn : 'el t -> 'el heap_el
top_heap_el_exn heap
Raises Empty if heap is empty.
Returns the top heap element of heap without changing it.
val fold_el : 'a t -> init:'b -> f:('b -> 'a heap_el -> 'b) -> 'b
fold_el heap ~f fold over heap with function f. The elements are passed in an unspecified order.
val iter_el : 'a t -> f:('a heap_el -> unit) -> unit
iter_el heap ~f iterate over heap with function f. The elements are passed in an unspecified order.

Destructive heap accessors

val pop : 'el t -> 'el option
pop heap
Returns Some top_element of heap, removing it, or None if heap is empty.
val pop_exn : 'el t -> 'el
pop_exn heap
Raises Empty if heap is empty.
Returns the top element of heap, removing it.
val pop_heap_el : 'el t -> 'el heap_el option
pop_heap_el heap
Returns Some top_heap_element, removing it, or None if heap is empty.
val pop_heap_el_exn : 'el t -> 'el heap_el
pop_heap_el_exn heap
Raises Empty if heap is empty.
Returns the top heap element of heap, removing it.
val cond_pop : 'el t -> ('el -> bool) -> 'el option
cond_pop heap cond
Returns Some top_element of heap if it fills condition cond, removing it, or None in any other case.
val cond_pop_heap_el : 'el t -> ('el -> bool) -> 'el heap_el option
cond_pop_heap_el heap cond
Returns Some top_heap_element of heap if the associated element fills condition cond, removing it, or None in any other case.
val push : 'el t -> 'el -> 'el heap_el
push heap el pushes element el on heap.
Returns the heap element associated with the newly inserted element.
val push_heap_el : 'el t -> 'el heap_el -> unit
push_heap_el heap heap_el pushes heap_el on heap.
Raises Failure if heap_el is already member of some heap.
val remove : 'el heap_el -> unit
remove heap_el removes heap_el from its associated heap.
Raises Failure if heap_el is not member of any heap.
val update : 'el heap_el -> 'el -> unit
update heap_el el updates heap_el with element el in its associated heap.
Raises Failure if heap_el is not member of any heap.

For testing only.

val check_heap_property : 'el t -> bool
check_heap_property h asserts that h has the heap property: that all nodes are less than their children by h's comparison function.
val sexp_of_t : ('el -> Sexplib.Sexp.t) -> 'el t -> Sexplib.Sexp.t
val sexp_of_heap_el : ('el -> Sexplib.Sexp.t) -> 'el heap_el -> Sexplib.Sexp.t
Type of heap elements (they can be efficiently removed)

Functions on heap elements


heap_el_is_valid heap_el

heap_el_get_el heap_el

heap_el_get_heap_exn heap_el

Information on heap values


get_cmp heap

Heap creation


create ?min_size cmp

of_array ?min_size cmp ar

copy heap

Search functions


mem heap el

heap_el_mem heap heap_el

find_heap_el_exn heap el

Non-destructive heap accessors


top heap

top_exn heap

top_heap_el heap

top_heap_el_exn heap

fold_el heap ~f fold over heap with function f. The elements are passed in an unspecified order.

iter_el heap ~f iterate over heap with function f. The elements are passed in an unspecified order.

Destructive heap accessors


pop heap

pop_exn heap

pop_heap_el heap

pop_heap_el_exn heap

cond_pop heap cond

cond_pop_heap_el heap cond

push heap el pushes element el on heap.

push_heap_el heap heap_el pushes heap_el on heap.

remove heap_el removes heap_el from its associated heap.

update heap_el el updates heap_el with element el in its associated heap.

For testing only.


check_heap_property h asserts that h has the heap property: that all nodes are less than their children by h's comparison function.