Module PathVisual.MutBinHeap

module MutBinHeap: sig .. end

Mutable binary heap of (int * int) * int * float using hash table for fast delete

type pos = int * int

type elt = pos * int * float

type arrayidx = int

type t = {

	`mutable last : arrayidx;`
	`mutable arr : elt array;`
	`hash : arrayidx PathVisual.IntPairHash.t;`
	`compare : elt -> elt -> int;`

}

val get : t ->
       arrayidx -> elt

val parent : arrayidx -> arrayidx

Get array index of parent

val left_child : arrayidx -> arrayidx

Get array index of left child

val right_child : arrayidx -> arrayidx

Get array index of right child

val getpos : t ->
       PathVisual.IntPairHash.key -> elt

Get element with given pos

val swap : t ->
       arrayidx -> arrayidx -> unit

Swaps 2 array indexes

val bubbleup : t -> arrayidx -> unit

val bubbledown : t -> arrayidx -> unit

val make : (elt -> elt -> int) ->
       t

Make a new binary heap.

make (fun ((x,y),cost,dist)
         ((x',y'),cost',dist') -> compare ((float cost)
         +. dist) ((float cost') +. dist'))

makes a binary heap comparing cost + distance (A* )

val insert : t -> elt -> unit

Insert element into heap

val remove : t -> PathVisual.IntPairHash.key -> unit

Remove element

((x,y),cost,dist)

where

(x,y) = pos

val replace : t -> elt -> unit

Insert new element or replace existing element with matching first.

replace heap ((2,0),2,3.0)

would replace the existing element

((2,0),3,5.0)

val pop : t -> elt

Returns the minimum element and removes it from the heap.