Module Heap

module Heap: Heap

Exceptions

exception Empty

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

Types

type 'el t

Type of heaps

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.

Information on heap values

val length : 'el t -> int

length heap
Returns the length (number of elements) of heap.

val is_empty : 'el t -> bool

is_empty heap
Returns true iff heap does not contain any elements.

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 iter : 'a t -> f:('a -> unit) -> unit

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