Manipulate heap

Learning
1

Hi, I want to use pairing_heap in core_kernel library to implement a min heap. However, there are some code I don’t quite understand.

In addition to the typical add, pop, top functions pairing_heap provided, there is also a module Elt. I guess people want to use this module to access and manipulate elements in queue more conveniently. However, I don’t know how to define my own type to meet corresponding function signature.

module Elt : sig
  type 'a t [@@deriving sexp_of]

  (** [value_exn t] returns the value in the heap controlled by this token if the
      value is still in the heap, and raises otherwise. *)
  val value_exn : 'a t -> 'a
end

Let’s say I have a type as below

type node = {
name : string;
mutable order : int;
}

The corresponding comparison function is

let node_cmp t1 t2 = Int.compare t1.order t2.order;;

Then I can create a heap from list

let heap = Heap.of_list [{name = "a"; order = 0}; 
                         {name = "b"; order = 1}; 
                         {name = "c"; order = 2}] 
                         ~cmp:node_cmp

Now I want to update order of node b to 3. I noticed there is a function with signature

(** [update t token v] is shorthand for [remove t token; add_removable t v]. *)
val update : 'a t -> 'a Elt.t -> 'a -> 'a Elt.t

'a in this case is type node apparently. However, how can I get a token with type 'a Elt.t?

Any help would be appreciated, thank you in advance!

2

If you insert an element with Pairing_heap.add_removable, you will receive an Elt.t in response.

1 Like
3

You are right. Why do we differentiate Pairing_heap.add and Pairing_heap.add_removable in this case? I feel like they have the same goal. Is there any insight behind it?

4

They have different performance characteristics; see the reference to allocation on the doc comment for add_removable. And in a lot of cases you don’t care about the Elt.t and you’re just going to ignore it, so it’s convenient to have a unit-returning version.

1 Like