Heaps v0.1.0

MakeHeap<T>

pub func MakeHeap<T>(items: var T[..])

Rearranges items into a max-heap. items is borrowed mutably and rewritten. Fewer than two elements are already a heap. The arrangement is not an order: only the first element ends up where a sorted sequence would put it. Requires < on the element type. Cannot fail. Runs in time proportional to the length — linear, not n log n, because sifting from the bottom up does most of its work on the short subtrees near the leaves. Allocates nothing.

Source

Type parameters

Parameters

PushHeap<T>

pub func PushHeap<T>(items: var T[..])

Restores the heap property after an element has been appended to items. items is borrowed mutably and rewritten; it must be the whole heap including the new last element, and everything before that element must already be a heap. An empty view does nothing. The caller appends and this repairs, because appending is the storage owner's business. Requires < on the element type. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

PopHeap<T>

pub func PopHeap<T>(items: var T[..])

Moves the largest element of items to its end and restores the heap property over the rest. items is borrowed mutably and rewritten. Afterwards the largest element sits at the last position and the first length - 1 positions are a heap again; the caller is what shortens the sequence, or leaves the element there. Fewer than two elements do nothing. Requires < on the element type. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

SortHeap<T>

pub func SortHeap<T>(items: var T[..])

Turns the heap items into a sorted sequence, smallest first. items is borrowed mutably and rewritten; it must already be a heap, which MakeHeap is what makes it. Repeated popping, which is exactly heapsort. A sequence that is not a heap does not fail; it comes out rearranged and not sorted. Requires < on the element type. Cannot fail. Makes O(n log n) comparisons and allocates nothing. Equal elements may be reordered.

Source

Type parameters

Parameters

IsHeap<T>

pub func IsHeap<T>(items: T[..]) -> bool

Whether items is arranged as a max-heap. items is borrowed and read. An empty sequence and a single element are heaps, there being no pair to violate the property. Requires < on the element type. Cannot fail. Runs in time proportional to the length and allocates nothing.

Source

Type parameters

Parameters

Returns: whether the sequence satisfies the heap property throughout

IsHeapUntil<T>

pub func IsHeapUntil<T>(items: T[..]) -> uint

How much of items from the front is arranged as a max-heap. items is borrowed and read. Returns the length when the whole sequence is a heap, and otherwise the index of the first element larger than its parent. Requires < on the element type. Cannot fail. Runs in time proportional to the answer and allocates nothing.

Source

Type parameters

Parameters

Returns: how many leading elements satisfy the heap property

MakeHeapBy<T>

pub func MakeHeapBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Rearranges items into a max-heap under compare. items is borrowed mutably and rewritten; compare must be a strict weak ordering. Fewer than two elements are already a heap. Cannot fail. Runs in time proportional to the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

PushHeapBy<T>

pub func PushHeapBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Restores the heap property under compare after an element has been appended to items. items is borrowed mutably and rewritten; everything before its last element must already be a heap. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

PopHeapBy<T>

pub func PopHeapBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Moves the largest element of items under compare to its end and restores the heap over the rest. items is borrowed mutably and rewritten. The caller is what shortens the sequence afterwards. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

SortHeapBy<T>

pub func SortHeapBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Turns the heap items into a sequence sorted by compare, smallest first. items is borrowed mutably and rewritten and must already be a heap under the same comparison. Cannot fail. Makes O(n log n) comparisons and allocates nothing beyond whatever compare does. Equivalent elements may be reordered.

Source

Type parameters

Parameters

IsHeapBy<T>

pub func IsHeapBy<T>(
    items: T[..],
    compare: func(T, T) -> Ordering
) -> bool

Whether items is arranged as a max-heap under compare. items is borrowed and read. An empty sequence and a single element are heaps. Cannot fail. Runs in time proportional to the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: whether the sequence satisfies the heap property throughout under compare

IsHeapUntilBy<T>

pub func IsHeapUntilBy<T>(
    items: T[..],
    compare: func(T, T) -> Ordering
) -> uint

How much of items from the front is arranged as a max-heap under compare. items is borrowed and read. Returns the length when the whole sequence is a heap, and otherwise the index of the first element larger than its parent. Cannot fail. Runs in time proportional to the answer and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: how many leading elements satisfy the heap property under compare