堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

Heapsort.go

pachage heapsort

func Sort[T constraints.Ordered](buf []T) {
    n := len(buf)
    for i := (n - 1) / 2; i >= 0; i-- {
        minHeapFixdown[T](buf, i, n)
    }

    for i := n - 1; i > 0; i-- {
        temp := buf[0]
        buf[0] = buf[i]
        buf[i] = temp
        minHeapFixdown[T](buf, 0, i)
    }
}

func minHeapFixdown[T constraints.Ordered](a []T, i, n int) {
    j := 2*i+1
    for j < n {
        if j+1 < n && a[j+1] < a[j] {
            j++
        }

        if a[i] <= a[j] {
            break
        }

        temp := a[i]
        a[i] = a[j]
        a[j] = temp

        i = j
        j = 2*i + 1
    }
}