gleamy/leftist_heap

This module provides an implementation of the leftist heap data structure, a type of binary 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)

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), item: a) -> Heap(a)

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

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(log n)

new

</>

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

Creates a new empty heap with the provided comparison function.