heap.go

heap sort in golang

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func heapSort(arr []int, l int) {
	for i := l / 2; i >= 0; i-- {
		heapify(arr, i, l)
	}
	k := l
	for k > 0 {
		arr[0], arr[k] = arr[k], arr[0]
		k--
		heapify(arr, 0, k)
	}
}

func heapify(arr []int, current, cap int) {
	for {
		maxIndex, left, right := current, leftIndex(current), rightIndex(current)
		if left <= cap && arr[current] < arr[left] {
			maxIndex = left
		}
		if right <= cap && arr[maxIndex] < arr[right] {
			maxIndex = right
		}
		if current == maxIndex {
			break
		}
		arr[current], arr[maxIndex] = arr[maxIndex], arr[current]
		current = maxIndex
	}
}

func leftIndex(current int) int {
	return current * 2
}

func rightIndex(current int) int {
	return current*2 + 1
}

func main() {
	s := generateSlice(10)
	fmt.Println("Unsorted", s)
	heapSort(s, len(s)-1)
	fmt.Println("Sorted", s)

}

func generateSlice(size int) []int {
	slice := make([]int, size, size)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < size; i++ {
		slice[i] = rand.Intn(99999) - rand.Intn(99999)
	}
	return slice
}