F# FormattingHeap<'T>
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
| Constructor | Description |
new(isDescending, length, data)
Signature: (isDescending:bool * length:int * data:HeapData<'T>) -> Heap<'T>
|
|
Instance members
| Instance member | Description |
Head
Signature: 'T
|
O(1) worst case. Returns the min or max element. |
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. |
IsEmpty
Signature: bool
|
O(1). Returns true if the heap has no elements. |
Length
Signature: int
|
O(n). Returns the count of elememts. |
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. |
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. |
