package core:slice/heap
Source

⌘K
Ctrl+K
or
/

    Overview

    Package implements a generic max heap in-place on a slice for any type.

    Index

    Types (0)

    This section is empty.

    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedure Groups (0)

    This section is empty.

    Types

    This section is empty.

    Constants

    This section is empty.

    Variables

    This section is empty.

    Procedures

    is_heap ¶
    Source

    is_heap :: proc(data: []$T, less: proc(a, b: $T) -> bool) -> bool {…}
     

    Checks if a given slice is a max heap.

    At most O(n) comparisons where N = len(data) will be performed.

    is_heap_until ¶
    Source

    is_heap_until :: proc(data: []$T, less: proc(a, b: $T) -> bool) -> int {…}
     

    Examines the slice and finds the largest range which is a max-heap. Elements are compared with user-supplied comparison procedure.

    This returns the upper bound of the largest range in the slice which is a max heap. That is, the last index for which data is a max heap.

    At most O(n) comparisons where N = len(data) will be performed.

    make ¶
    Source

    make :: proc(data: []$T, less: proc(a, b: $T) -> bool) {…}
     

    Constructs a max heap in slice given by data with comparator. A max heap is a range of elements which has the following properties:

    1. With N = len(data), for all 0 < i < N, data[(i - 1) / 2] does not compare less than data[i].

    2. A new element can be added using push in O(log n) time.

    3. The first element can be removed using pop in O(log n) time.

    The comparator compares elements of type T and can be used to construct a max heap (less than) or min heap (greater than) for T.

    pop ¶
    Source

    pop :: proc(data: []$T, less: proc(a, b: $T) -> bool) {…}
     

    Swaps the value in position data[0] and the value in data[len(data)-1] and makes subrange [0, len(data)-1) into a heap. This has the effect of removing the first element from the heap.

    At most 2 * log(N) comparisons where N = len(data) will be performed.

    push ¶
    Source

    push :: proc(data: []$T, less: proc(a, b: $T) -> bool) {…}
     

    Inserts the element at the position len(data)-1 into the max heap with comparator.

    At most log(N) comparisons where N = len(data) will be performed.

    sort ¶
    Source

    sort :: proc(data: []$T, less: proc(a, b: $T) -> bool) {…}
     

    Converts the max heap into a sorted range in ascending order. The resulting slice will no longer be a heap after this.

    At most 2 N log(N) comparisons where N = len(data) will be performed.

    Procedure Groups

    This section is empty.

    Source Files

    Generation Information

    Generated with odin version dev-2024-12 (vendor "odin") Windows_amd64 @ 2024-12-17 21:11:01.221995700 +0000 UTC