FSharpx.Collections


PairingHeap<'T> Type

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 case Description

E bool

Full Usage: E bool

Parameters:
    Item : bool

Item : bool

T(bool, 'T, PairingHeap<'T> list)

Full Usage: T(bool, 'T, PairingHeap<'T> list)

Parameters:
Item1 : bool
Item2 : 'T
Item3 : PairingHeap<'T> list

Instance members

Instance member Description

this.Head()

Full Usage: this.Head()

Returns: 'T

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

Returns: 'T

this.Insert(x)

Full Usage: this.Insert(x)

Parameters:
    x : 'T

Returns: PairingHeap<'T>

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

x : 'T
Returns: PairingHeap<'T>

this.IsDescending

Full Usage: this.IsDescending

Returns: bool

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

Returns: bool

this.IsEmpty

Full Usage: this.IsEmpty

Returns: bool

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

Returns: bool

this.Length()

Full Usage: this.Length()

Returns: int

O(n). Returns the count of elements.

Returns: int

this.Merge(xs)

Full Usage: this.Merge(xs)

Parameters:
Returns: PairingHeap<'T>

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

xs : PairingHeap<'T>
Returns: PairingHeap<'T>

this.Tail()

Full Usage: this.Tail()

Returns: PairingHeap<'T>

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

Returns: PairingHeap<'T>

this.TryGetHead()

Full Usage: this.TryGetHead()

Returns: 'T option

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

Returns: 'T option

this.TryGetTail()

Full Usage: this.TryGetTail()

Returns: PairingHeap<'T> option

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

Returns: PairingHeap<'T> option

this.TryMerge(xs)

Full Usage: this.TryMerge(xs)

Parameters:
Returns: PairingHeap<'T> option

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

xs : PairingHeap<'T>
Returns: PairingHeap<'T> option

this.TryUncons()

Full Usage: this.TryUncons()

Returns: ('T * PairingHeap<'T>) option

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

Returns: ('T * PairingHeap<'T>) option

this.Uncons()

Full Usage: this.Uncons()

Returns: 'T * PairingHeap<'T>

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

Returns: 'T * PairingHeap<'T>