fsprojects/FSharpx.Collections


Heap<'T>

Namespace: FSharpx.Collections

Heap is an ordered linear structure where the ordering is either ascending or descending. "head" inspects the first element in the ordering, "tail" takes the remaining structure after head, and "insert" places elements within the ordering. PriorityQueue is available as an alternate interface. According to Okasaki the time complexity of the heap functions in this Heap implementation (based on the "pairing" heap) have "resisted" time complexity analysis.

Constructors

ConstructorDescription
new(isDescending, length, data)
Signature: (isDescending:bool * length:int * data:HeapData<'T>) -> Heap<'T>

CompiledName: .ctor

Instance members

Instance memberDescription
Head
Signature: 'T

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

CompiledName: get_Head

Insert(x)
Signature: x:'T -> Heap<'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: int

O(n). Returns the count of elememts.

CompiledName: get_Length

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

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

Rev()
Signature: unit -> Heap<'T>

O(n log n). Returns heap reversed.

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

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

TryHead
Signature: 'T option

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

CompiledName: get_TryHead

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

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

TryTail()
Signature: unit -> Heap<'T> option

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

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

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

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

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

Fork me on GitHub