Adding Heap-sort implemented in Go

prateekpandey14 · prateekpandey14 · commit b185489fde65 · 2017-10-06T14:07:25.000+05:30
diff --git a/HeapSort/Go/heap-sort.go b/HeapSort/Go/heap-sort.go
@@ -0,0 +1,75 @@
+package main
+
+import (
+	"fmt"
+	"math/rand"
+	"time"
+)
+
+func main() {
+	var heap *Heap
+	slice := generateSlice(20)
+	fmt.Println("\n--- Unsorted --- \n\n", slice)
+	heap.HeapSort(slice)
+	fmt.Println("\n--- Sorted ---\n\n", slice)
+}
+
+// Generates a slice of size, size filled with random numbers
+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(999) - rand.Intn(999)
+	}
+	return slice
+}
+
+type Heap struct {
+}
+
+func (heap *Heap) HeapSort(array []int) {
+	heap.BuildHeap(array)
+
+	for length := len(array); length > 1; length-- {
+		heap.RemoveTop(array, length)
+	}
+}
+
+func (heap *Heap) BuildHeap(array []int) {
+	for i := len(array) / 2; i >= 0; i-- {
+		heap.Heapify(array, i, len(array))
+	}
+}
+
+func (heap *Heap) RemoveTop(array []int, length int) {
+	var lastIndex = length - 1
+	array[0], array[lastIndex] = array[lastIndex], array[0]
+	heap.Heapify(array, 0, lastIndex)
+}
+
+func (heap *Heap) Heapify(array []int, root, length int) {
+	var max = root
+	var l, r = heap.Left(array, root), heap.Right(array, root)
+
+	if l < length && array[l] > array[max] {
+		max = l
+	}
+
+	if r < length && array[r] > array[max] {
+		max = r
+	}
+
+	if max != root {
+		array[root], array[max] = array[max], array[root]
+		heap.Heapify(array, max, length)
+	}
+}
+
+func (*Heap) Left(array []int, root int) int {
+	return (root * 2) + 1
+}
+
+func (*Heap) Right(array []int, root int) int {
+	return (root * 2) + 2
+}
