package main
 
import (
    "container/vector";
    "flag";
    "rand";
    "time";
)
 
var num = flag.Int("n", 10, "number of elements to heap sort")
 
func main() {
    flag.Parse();
    rand.Seed(time.Nanoseconds());
    v := vector.NewIntVector(*num);
    for i := 1; i <= *num; i++ {
        v.Set(i - 1, rand.Int() % 100)
    }
    heapSort(v);
    printHeap(v, 0, 0);
}
 
func left(i int) int {
    return i * 2 + 1
}
 
func right(i int) int {
    return i * 2 + 2
}
 
func parent(i int) int {
    return (i - 1) / 2
}
 
// Swap vec[i] with its parent if its larger. Stop at the top.
func maxHeapify(vec *vector.IntVector, i int) {
    if i <= 0 {
        return
    }
    p := parent(i);
    if vec.At(p) < vec.At(i) {
        temp := vec.At(p);
        vec.Set(p, vec.At(i));
        vec.Set(i, temp);
        maxHeapify(vec, p);
    }
}
 
// Given a list of numbers in any order, max heap sort it.
func heapSort(vec *vector.IntVector) {
    for i := 0; i < vec.Len(); i++ {
        maxHeapify(vec, i)
    }
}
 
func printHeap(vec *vector.IntVector, i int, nest int) {
    if i >= vec.Len() {
        return
    }
    for n := 0; n < nest; n++ {
        print("    ")
    }
    print(vec.At(i));
    print("\n");
    printHeap(vec, left(i), nest + 1);
    printHeap(vec, right(i), nest + 1);
}