// 15. hét – Kupacrendezés
// Futtatás: go run ./h15/heapsort
package main

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

func siftDown(a []int, i, n int) {
	for 2*i+1 < n {
		c := 2*i + 1
		if c+1 < n && a[c+1] > a[c] {
			c++
		}
		if a[i] >= a[c] {
			return
		}
		a[i], a[c] = a[c], a[i]
		i = c
	}
}

func heapSort(a []int, trace bool) {
	n := len(a)
	for i := n/2 - 1; i >= 0; i-- { // kupacépítés – O(n)
		siftDown(a, i, n)
	}
	if trace {
		fmt.Println("  kupac:    ", a)
	}
	for end := n - 1; end > 0; end-- { // a maximum a végére
		a[0], a[end] = a[end], a[0]
		siftDown(a, 0, end)
	}
}

func main() {
	a := []int{40, 70, 20, 90, 50, 80, 60, 10}
	fmt.Println("  kezdet:   ", a)
	heapSort(a, true)
	fmt.Println("  rendezett:", a)

	big := make([]int, 1_000_000)
	r := rand.New(rand.NewSource(1))
	for i := range big {
		big[i] = r.Int()
	}
	t0 := time.Now()
	heapSort(big, false)
	fmt.Printf("1 000 000 elem kupacrendezése: %.1f ms\n", float64(time.Since(t0).Microseconds())/1000)
}