fsprojects/FSharpx.Collections


PairingHeap<'T>

Namespace: FSharpx.Collections.Experimental

PairingHeap performs extremely well in practice, however (according to Okasaki) it should be avoided for applications taking advantage of persistence. Also according to Okasaki the time complexity of the heap functions in the PairingHeap implementation have "resisted" time complexity analysis. ofSeq: superior performance; insert: superior performance; tail: superior performance

Union Cases

Union CaseDescription
E(bool)
Signature: bool
T(bool,'T,PairingHeap<'T> list)
Signature: bool * 'T * PairingHeap<'T> list

Instance members

Instance memberDescription
Head()
Signature: unit -> 'T

O(1) worst case. Returns the min or max element.

Insert(x)
Signature: x:'T -> PairingHeap<'T>

O(log n) amortized time. Returns a new heap with the element inserted.

IsDescending
Signature: bool

O(1). Returns true if the heap has max element at head.

CompiledName: get_IsDescending

IsEmpty
Signature: bool

O(1) Returns true if the heap has no elements.

CompiledName: get_IsEmpty

Length()
Signature: unit -> int

O(n). Returns the count of elememts.

Merge(xs)
Signature: xs:PairingHeap<'T> -> PairingHeap<'T>

O(log n) amortized time. Returns heap from merging two heaps, both must have same descending.

Tail()
Signature: unit -> PairingHeap<'T>

O(log n) amortized time. Returns a new heap of the elements trailing the head.

TryGetHead()
Signature: unit -> 'T option

O(1) worst case. Returns option first min or max element.

TryGetTail()
Signature: unit -> PairingHeap<'T> option

O(log n) amortized time. Returns option heap of the elements trailing the head.

TryMerge(xs)
Signature: xs:PairingHeap<'T> -> PairingHeap<'T> option

O(log n) amortized time. Returns heap option from merging two heaps.

TryUncons()
Signature: unit -> ('T * PairingHeap<'T>) option

O(log n) amortized time. Returns option head element and tail.

Uncons()
Signature: unit -> 'T * PairingHeap<'T>

O(log n) amortized time. Returns the head element and tail.

Fork me on GitHub