heap_sort.go

//usr/bin/env go run $0 $@ ; exit

package main

import (
    "fmt"
    "math/rand"
)

type BinaryHeap struct {
    nr_elem int
    data []int
}

func make_heap() *BinaryHeap {
    heap := new(BinaryHeap)
    heap.data = make([]int, 1024)
    heap.nr_elem = 0

    return heap
}

func (heap *BinaryHeap) push(x int) {
    if heap.nr_elem == len(heap.data) {
        heap.data = heap.data[0:len(heap.data)*2]
    }

    heap.data[heap.nr_elem] = x
    heap.nr_elem ++
    heap.upheap(heap.nr_elem) // 1-origin idx
}

func (heap *BinaryHeap) pop() int {
    if heap.nr_elem == 0 {
        panic("no more element")
    }
    ret := heap.data[0]
    heap.data[0] = heap.data[heap.nr_elem - 1]
    heap.nr_elem --
    heap.downheap(1) // 1-origin idx

    return ret
}

// NOTICE: idx is 1-origin numbering
func (heap *BinaryHeap) upheap(idx int) {
    for idx > 1 {
        p_idx := idx / 2
        if heap.data[p_idx - 1] > heap.data[idx - 1] {
            heap.data[p_idx - 1], heap.data[idx - 1] = heap.data[idx - 1], heap.data[p_idx - 1]
            idx /= 2
        } else {
            break
        }
    }
    return
}

// NOTICE: idx is 1-origin numbering
func (heap *BinaryHeap) downheap(idx int) {
    for idx * 2 <= heap.nr_elem {
        lc_idx := idx * 2
        rc_idx := idx * 2 + 1
        c_idx := lc_idx

        if rc_idx <= heap.nr_elem && heap.data[rc_idx - 1] < heap.data[lc_idx - 1] {
            c_idx = rc_idx
        }

        if heap.data[c_idx - 1] < heap.data[idx - 1] {
            heap.data[c_idx - 1], heap.data[idx - 1] = heap.data[idx - 1], heap.data[c_idx - 1]
        }

        idx = c_idx
    }
    return
}

func heap_sort(data []int) []int {
    heap := make_heap()
    ret_data := make([]int, len(data))

    for _, x := range data {
        heap.push(x)
    }

    for i, _ := range ret_data {
        ret_data[i] = heap.pop()
    }

    return ret_data
}

func main() {
    rand.Seed(0)

    for n := 0; n < 100; n++ {
        // generate random number array
        var data = make([]int, 20)
        for i, _ := range data {
            data[i] = rand.Intn(100)
        }

        fmt.Println(data)

        // sort by Quick Sort
        data = heap_sort(data)
        
        fmt.Println(data)
        
        // check whether the array is sorted.
        for i := 0; i < len(data) - 1; i++ {
            if data[i] > data[i + 1] {
                panic(i)
            }
        }
    }
}