Skip to content
This repository
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 132 lines (106 sloc) 4.163 kb
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
(*
* Heap -- binomial heaps
* Copyright (C) 2011 Batteries Included Development Team
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version,
* with the special exception on linking described in file LICENSE.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*)

(** Functional heaps over ordered types

Ascribes to:

[BatEnum.Enumerable with type 'a enumerable = 'a t]
*)

type +'a t
  (** Heap of elements that are compared with [Pervasives.compare]. *)

val size : 'a t -> int
  (** Number of elements in the heap. O(1) *)

(** {6 Construction} *)

val empty : 'a t
  (** The empty heap. *)

val insert : 'a t -> 'a -> 'a t
  (** Insert an element into the heap. Duplicates are kept. O(log m) *)

val add : 'a -> 'a t -> 'a t
  (** [add x h] is the same as [insert h x]. This function is intended
to be used with [fold_right]. *)

(** {6 Operations} *)

val merge : 'a t -> 'a t -> 'a t
  (** Merge two heaps. O(log m) *)

val find_min : 'a t -> 'a
  (** Find the minimal element of the heap. O(1)
@raise Invalid_argument ["find_min"] if the heap is empty *)

val del_min : 'a t -> 'a t
  (** Delete the minimal element of the heap. O(log n)
@raise Invalid_argument ["del_min"] if the heap is empty *)

(** {6 Transformation} *)

val of_list : 'a list -> 'a t
  (** Build a heap from a given list. O(n log n) *)

val to_list : 'a t -> 'a list
  (** Enumerate the elements of the heap. O(n log n) *)

val elems : 'a t -> 'a list
  (** @deprecated Same as [to_list]. *)

val of_enum : 'a BatEnum.t -> 'a t
  (** Build a heap from an enumeration. Consumes the enumeration.
O(n log n) *)

val enum : 'a t -> 'a BatEnum.t
  (** Enumerate the elements of the heap in heap order. O(log n) per
{!BatEnum.get}. *)

(** {6 Printing} *)

val print : ?first:string -> ?last:string -> ?sep:string
  -> ('a BatInnerIO.output -> 'b -> unit)
  -> 'a BatInnerIO.output -> 'b t -> unit
  (** Print the contents of the heap in heap order. O(n log n) *)

val t_printer : 'a BatValuePrinter.t -> 'a t BatValuePrinter.t
  (** See {!BatValuePrinter}. *)

(** {6 Functorized version} *)

(** The result of {!Make} *)
module type H =
sig
  type elem
    (** Type of elements of the heap *)
  type t
    (** Type of the heap *)
  val empty : t
    (** See {!BatHeap.empty}. *)
  val size : t -> int
    (** See {!BatHeap.size}. *)
  val insert : t -> elem -> t
    (** See {!BatHeap.add}. *)
  val add : elem -> t -> t
    (** See {!BatHeap.insert}. *)
  val merge : t -> t -> t
    (** See {!BatHeap.merge}. *)
  val find_min : t -> elem
    (** See {!BatHeap.find_min}. *)
  val del_min : t -> t
    (** See {!BatHeap.del_min}. *)
  val of_list : elem list -> t
    (** See {!BatHeap.of_list}. *)
  val to_list : t -> elem list
    (** See {!BatHeap.to_list}. *)
  val elems : t -> elem list
    (** @deprecated Same as [to_list]. *)
  val of_enum : elem BatEnum.t -> t
    (** See {!BatHeap.of_enum}. *)
  val enum : t -> elem BatEnum.t
    (** See {!BatHeap.enum}. *)
  val print : ?first:string -> ?last:string -> ?sep:string
    -> ('a BatInnerIO.output -> elem -> unit)
    -> 'a BatInnerIO.output -> t -> unit
    (** See {!BatHeap.print}. *)
  val t_printer : elem BatValuePrinter.t -> t BatValuePrinter.t
    (** See {!BatHeap.t_printer}. *)
end

module Make (Ord : BatInterfaces.OrderedType) : H with type elem = Ord.t
  (** Functorized heaps over arbitrary orderings. All the functions have
the same complexity as the non-functorized versions. *)
Something went wrong with that request. Please try again.