package core:slice/heap
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 ¶
is_heap :: proc "odin" (data: []$T, less: proc "odin" (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 ¶
is_heap_until :: proc "odin" (data: []$T, less: proc "odin" (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 ¶
make :: proc "odin" (data: []$T, less: proc "odin" (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 ¶
pop :: proc "odin" (data: []$T, less: proc "odin" (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 ¶
push :: proc "odin" (data: []$T, less: proc "odin" (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.
Procedure Groups
This section is empty.
Source Files
Generation Information
Generated with odin version dev-2023-03 (vendor "odin") Windows_amd64 @ 2023-03-29 21:09:05.455642500 +0000 UTC