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

Collection Info

View Source
Collection
core
Path
slice/heap
Entries
6
Constants 0
Types 0
Procedures 6
Jump to Procedures
is_heap is_heap_until make pop push sort
Procedure Groups 0
Variables 0

Source Files

Procedures

6

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.