What is the difference between Core_kernel.Heap and Core_kernel.FHeap?

Question

Jane Street's Core_kernel library has two heap implementations based on pairing heaps:

Module Core_kernel.Heap

Heap implementation based on a pairing-heap.

(docs)

Module Core_kernel.Fheap

Functional heaps (implemented as pairing heaps).

(docs)

From the descriptions, it's not clear to me what the difference is between them. When would I use one or the other?

Answer 1

The difference resides in the word "Functional" in your second quote: Heap is an imperative implementation, which can also be seen by the signature of e.g. the add function:

val add : 'a t ‑> 'a ‑> Core_kernel__.Import.unit

which returns unit, and modifies in place the existing heap.

On the other hand FHeap is functional, meaning that operations such as add will create new objects, leaving the original intact: in this case, the signature for add is

val add : 'a t ‑> 'a ‑> 'a t