gleamy/pairing_heap

This module provides an implementation of the pairing heap data structure, a type of self-adjusting heap with efficient insert, find_min, and delete_min, and merge operations.

Types

Heap

opaque </>

pub opaque type Heap(a)

Functions

delete_min

</>

pub fn delete_min(heap: Heap(a)) -> Result(#(a, Heap(a)), Nil)

Removes and returns the minimum element from the heap along with the new heap after deletion, if the heap is not empty. Time complexity: O(log n) amortized

find_min

</>

pub fn find_min(heap: Heap(a)) -> Result(a, Nil)

Returns the minimum element in the heap, if the heap is not empty. Time complexity: O(1)

insert

</>

pub fn insert(heap: Heap(a), key: a) -> Heap(a)

Inserts a new item into the heap, preserving the heap property. Time complexity: O(1)

merge

</>

pub fn merge(heap1: Heap(a), heap2: Heap(a)) -> Heap(a)

Merges two heaps into a new heap containing all elements from both heaps, preserving the heap property. The given heaps must have the same comparison function. Time complexity: O(1)

new

</>

pub fn new(compare: fn(a, a) -> Order) -> Heap(a)

Creates a new empty heap with the provided comparison function.