package main
import (
"fmt"
"math"
)
func parent(i int) int {
return i >> 1
}
func left(i int) int {
return i << 1
}
func right(i int) int {
return i<<1 + 1
}
func buildMaxHeap(array []int) {
heapSize := len(array) - 1
for i := heapSize / 2; i > 0; i-- {
maxHeapify(array, heapSize, i)
}
}
func maxHeapify(array []int, heapSize, i int) {
l, r := left(i), right(i)
largest := i
if l <= heapSize && array[l] > array[i] {
largest = l
}
if r <= heapSize && array[r] > array[largest] {
largest = r
}
if largest != i {
array[largest], array[i] = array[i], array[largest]
maxHeapify(array, heapSize, largest)
}
}
func printArray(array []int) {
for i := 1; i < len(array); i = i << 1 {
for k := 0; k < i && k+i < len(array); k++ {
fmt.Print(array[i+k], " ")
}
fmt.Println()
}
}
func heapSort(array []int) {
buildMaxHeap(array)
heapSize := len(array) - 1
for i := len(array) - 1; i > 1; i-- {
array[i], array[1] = array[1], array[i]
heapSize--
maxHeapify(array, heapSize, 1)
}
}
func main() {
arr := []int{math.MaxInt64, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}
printArray(arr)
buildMaxHeap(arr)
printArray(arr)
heapSort(arr)
fmt.Println(arr)
}
image.png
