堆排序

这里的堆不是编程语言里的堆，是一种数据结构。

堆像一棵倒立的满二叉树，每个节点最多有两个直接子节点。最上面的节点称为根节点，没有子节点的节点称为叶子节点，有子节点的节点称为分支节点。

堆有大顶堆和小顶堆之分。大顶堆是指分支节点大于它的所有子节点，堆里最大元素是根节点；小顶堆是指分支节点小于它的所有子节点，堆里最小元素是根节点。

堆排序是借助堆数据结构进行排序的一种高效算法，它的平均时间复杂度是O(n*lg(n))。

实现

堆排序的核心是构建和维持堆。

实现时要注意的是：

• 以数组第一个节点（序号为0）为根，方便计算叶子节点。

• 大多数算法介绍都是以1为数组的起始下标的，左右叶子节点的计算分别为：lchild=2*parent; rchild =2*parent+1；而实际编程语言大多数都是以0为起始下标的，所以子节点计算需要调整为：lchild=2*parent+1; rchild=2*parent+2；因为根节点是0，导致根节点的左子树与根节点相同而出错。

• 构建是从底向上逐层构建堆，从最后一层的分支节点（ len(arr)/2 ）开始构建堆。

• 从堆顶取出最大元素与最后一个堆元素交互后，堆的大小减1。所以堆在排序过程中是逐渐缩小的，但根总是第一个元素，所以可以利用之前也构建好的堆，只需要调整一棵子树。
  

func left(parent int) int {
    return 2*parent + 1
}

func right(parent int) int {
    return 2*parent + 2
}

func MaxHeapify(arr []int, parent, heapSize int) {
    l, r, largest := left(parent), right(parent), parent
    if l < heapSize && arr[l] > arr[parent] {
        largest = l
    }

    if r < heapSize && arr[r] > arr[largest] {
        largest = r
    }

    if largest != parent {
        util.Swap(arr, parent, largest)
        MaxHeapify(arr, largest, heapSize)
    }
}

func BuildMaxHeap(arr []int) {
    for i, heapSize := len(arr)/2, len(arr); i >= 0; i-- {
        MaxHeapify(arr, i, heapSize)
    }
}

func HeapSort(arr []int) {
    BuildMaxHeap(arr)
    for i := len(arr) - 1; i > 0; i-- {
        util.Swap(arr, 0, i)
        MaxHeapify(arr, 0, i)
    }
}

欢迎关注我的微信公众号: coderbee笔记，可以更及时回复你的讨论。