package core:slice/heap
Source

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 "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 ¶
Source

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 ¶
Source

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 ¶
Source

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 ¶
Source

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.

sort ¶
Source

sort :: proc "odin" (data: []$T, less: proc "odin" (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-03 (vendor "odin") Windows_amd64 @ 2023-03-29 21:09:05.455642500 +0000 UTC