package core:slice/heap

Source

Checks if a given slice is a max heap.

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

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.

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.

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.

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.

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.