(Ord: OrderedType) = struct

  

(*** types ***)


  type data = Ord.t

  type heap = {
    (* the heap *)
    mutable hp_heap: data array;

    (* number of elements in the heap,
       i.e. all elements of the array at index >= hp_length are invalid. *)
    mutable hp_length: int;

    (* null element used to fill empty array fields.
       avoids keeping them filled with removed older entries,
       so that those can be gargabe collected. *)
    hp_null_element: data;
  }

  type t = heap


  

(*** creation ***)



  let create (null_element: data) : heap = {
    hp_heap = [| |];
    hp_length = 0;
    hp_null_element = null_element;
  }



  

(*** access ***)



  let min (heap: heap) : data = 
    if heap.hp_length <= 0 then begin
      raise Not_found
    end;

    heap.hp_heap.(0)


  

(*** check ***)



  (* check that the heap ensures the invariant,
     i.e. has a proper structure and will return the minimum element *)
  let check (heap : heap) : unit =
    if Const.debug then begin
      for i = 0 to heap.hp_length - 1 do
        let left =
          (2 * i) + 1
        in
        let right =
        (2 * i) + 2
        in
          if left < heap.hp_length then begin
            if Ord.compare heap.hp_heap.(left) heap.hp_heap.(i) < 0 then begin
              failwith "Heap.check 1";
            end
          end;
          
          if right < heap.hp_length then begin
            if Ord.compare heap.hp_heap.(left) heap.hp_heap.(i) < 0 then begin
              failwith "Heap.check 2";
            end
          end;
      done
    end



  

(*** add ***)




  (* double the array length if it's exceeded *)
  let increase_heap_size (heap: heap) (data: data) : unit =
    if heap.hp_length >= Array.length heap.hp_heap then begin
      (* already set to max length during the last pass? *)
      if heap.hp_length = Sys.max_array_length then begin
        raise OVERFLOW;
      end;

      let new_size =
        let desired_size = 
          Tools.max_int 256 (2 * (Array.length heap.hp_heap))
        in
          (* obey the hard limit of the max. array size *)
          Pervasives.min Sys.max_array_length desired_size
      in
        let new_heap =
          Array.make new_size data
        in
          Array.blit heap.hp_heap 0 new_heap 0 (Array.length heap.hp_heap);
          heap.hp_heap <- new_heap;
    end


  (* a new element is added at the end.
     switch it with its parent element if it is smaller *)
  let rec sift_up (heap: heap) (data: data) (index: int) : unit =
    if index = 0 then begin
      heap.hp_heap.(index) <- data;
    end

    else begin
      let parent_index =
        (index - 1) / 2
      in
        if Ord.compare data heap.hp_heap.(parent_index) < 0 then begin
          heap.hp_heap.(index) <- heap.hp_heap.(parent_index);
          sift_up heap data parent_index
        end

        else begin
          heap.hp_heap.(index) <- data;
        end
    end


  let add (heap: heap) (data: data) : unit =
    increase_heap_size heap data;

    sift_up heap data heap.hp_length;

    heap.hp_length <- heap.hp_length + 1;
    
    check heap


  

(*** remove ***)



  (* the first element has been retrieved.
     so remove the last element, put it in front,
     and go down the tree while the last element is greater
     than the current node's children, switching it with the child.
     if it's smaller than the children, insert it *)
  let rec sift_down (heap: heap) (data: data) (index: int) : unit =
    let left_child_index =
      index * 2 + 1
    in
      (* at the bottom of the heap, so insert here *)
      if left_child_index > heap.hp_length then begin
        heap.hp_heap.(index) <- data;
      end
          
      else begin
        let right_child_index =
          index * 2 + 2
        in
            
        (* which of the two child nodes is smaller? *)
        let smaller_child_index =
          if right_child_index > heap.hp_length then begin
            left_child_index
          end
            
          else begin
            if Ord.compare heap.hp_heap.(left_child_index) heap.hp_heap.(right_child_index) <= 0 then
              left_child_index
            else
              right_child_index
          end
        in
          (* is data smaller than the smallest child? *)
          if Ord.compare data heap.hp_heap.(smaller_child_index) <= 0 then begin
            (* yes, so insert it here *)
            heap.hp_heap.(index) <- data;
          end

          else begin
            (* no, so replace with the smaller child and descend in its branch *)
            heap.hp_heap.(index) <- heap.hp_heap.(smaller_child_index);
            sift_down heap data smaller_child_index;
          end
        end


  let remove_min (heap: heap) : data = 
    if heap.hp_length <= 0 then begin
      raise Not_found
    end;

    let data =
      heap.hp_heap.(0)
    in
      heap.hp_length <- heap.hp_length - 1;
      
      if heap.hp_length > 0 then begin
        sift_down heap heap.hp_heap.(heap.hp_length) 0
      end;

      heap.hp_heap.(heap.hp_length) <- heap.hp_null_element;

      check heap;

      data
    


  

(*** iteration ***)



  let iter (func: data -> unit) (heap: heap) : unit =
    for i = 0 to heap.hp_length - 1 do
      func heap.hp_heap.(i)
    done



  

(*** size ***)


  let is_empty (heap: heap) : bool =
    heap.hp_length = 0
    

  let size (heap: heap) : int =
    heap.hp_length

end