-
Notifications
You must be signed in to change notification settings - Fork 0
/
fibheap.mli
36 lines (27 loc) · 1.28 KB
/
fibheap.mli
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type 'a fibTree
(** The type for the nodes of a Fibonacci heap. *)
type 'a fibHeap = {
mutable min : 'a fibTree Cdlist.cdlist
}
(** The type for Fibonacci heaps. *)
val make : unit -> 'a fibHeap
(** Creates a new, empty Fibonnaci heap. *)
val min : 'a fibHeap -> 'a * float
(** [min f] returns the cell containing the minimum of [f]. *)
val add : 'a -> float -> 'a fibHeap -> unit
(** [add e p f] adds an element of key [e] with priority [p] to the heap [f]. *)
val merge : 'a fibHeap -> 'a fibHeap -> 'a fibHeap
(** [merge f f'] merges the two heaps. *)
val decrease_priority : 'a fibTree Cdlist.cdlist -> float -> 'a fibHeap
(** [decrease_priority n p f] sets the priority of node [n] from heap [f]
to [p]. Make sure that [p] is smaller than the previous priority
of node [n] and that [n] is actually part of [f]. Behaviour is
undefined otherwise. *)
val delete : 'a fibTree Cdlist.cdlist -> float -> unit
(** [delete n f] deletes node [n] from heap [f]. Behaviour is
undefined if [n] is not in [f]. *)
val extract_min : 'a fibHeap -> 'a * float
(** [extract_min f] returns the element with the lowest priority,
along with its priority, and deletes it from f. *)
val iter : ('a fibTree Cdlist.cdlist) -> 'a fibHeap
(** [iter f h] applies [f] to each element of [h] *)