package core:slice/heap
⌘K
Ctrl+K
or
/
Overview
Package implements a generic max heap in-place on a slice for any type.
Types
This section is empty.
Constants
This section is empty.
Variables
This section is empty.
Procedures
is_heap ¶
Checks if a given slice is a max heap.
At most O(n) comparisons where N = len(data) will be performed.
is_heap_until ¶
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(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 ¶
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 ¶
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 ¶
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-2023-10 (vendor "odin") Windows_amd64 @ 2023-10-03 21:09:46.942519100 +0000 UTC