Function HeapSort

sort/heapsort.go:122–143

(slice []T)

}

func HeapSort[T constraints.Ordered](slice []T) []T {
	N := len(slice)

	moreFunc := func(i, j int) bool {
		return slice[i] > slice[j]
	}
	swapFunc := func(i, j int) {
		slice[i], slice[j] = slice[j], slice[i]
	}

	// build a maxheap
	for i := N/2 - 1; i >= 0; i-- {
		heapifyDown(slice, N, i, moreFunc, swapFunc)
	}

	for i := N - 1; i > 0; i-- {
		slice[i], slice[0] = slice[0], slice[i]
		heapifyDown(slice, i, 0, moreFunc, swapFunc)
	}

	return slice
}