堆排序

堆排序

堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列.
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列.

如下图：

因为我们常用数组来存储完全二叉树，所以我们也可以用数组来存储堆。
堆在数组中的存储图如下：

由上图我们可以看出对于堆中元素下标为i的点:

• 2*i+1为它的左子节点

• 2*i+2为它的右子节点

• i/2是它的前继节点
  

  算法原理

  堆排序的算法原理:

• 创建一个堆 H[0……n-1].

• 把堆首（最大值）和堆尾互换.

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置.

• 重复步骤2，直到堆的尺寸为 1.

堆排序算法实现:

func main()  {
    array := []int{52,16,37,2,3,32,12,27,19,42,29,13,37,12,9}
    HeapSort(array)
    fmt.Println("HeapSort:",array)
}
func HeapSort(array []int) {
    m := len(array)
    s := m/2
    for i := s; i > -1; i-- {
        heap(array, i, m-1)
    }
    for i := m-1; i > 0; i-- {
        array[i], array[0] = array[0], array[i]
        heap(array, 0, i-1)
    }
}
func heap(array []int, i, end int){
    l := 2*i+1
    if l > end {
        return
    }
    n := l
    r := 2*i+2
    if r <= end && array[r]>array[l]{
        n = r
    }
    if array[i] > array[n]{
        return
    }
    array[n], array[i] = array[i], array[n]
    heap(array, n, end)
}

运行结果:

HeapSort: [2 3 9 12 12 13 16 19 27 29 32 37 37 42 52]