golang实现堆排序

算法题：
给定一个整型数组，将数组的中的元素按升序排序。

基本思路：
操作：排序
输入：无序整型数组
输出：有序整型数组

这里操作采用堆排序算法，堆排序的基本步骤如下：

将整型数组构造成大顶堆结构
返回堆顶元素
减少堆的长度，有如下情形：
a. 若堆的长度等于0，跳转到第4步
b. 若堆的长度大于0，跳转到第2步
返回有序数组

堆排序算法有个关键步骤是构建堆的过程，堆的定义如下：

堆是一个满二叉树，根元素的值大于左右子树所有节点的值，并且左右子树也是一个堆

从堆的定义可以看出，堆的定义是一个递归定义，针对这种递归定义的数据结构，往往会涉及到递归算法。

对于树的构造，一般性的有两种方式，一种是自上而下，另一种是自下而上，至于采用那种方式方便，要依据具体的情况。堆的构造过程是自下而上的方式。这种方式有个好处，每个小堆是否满足堆的性质，只要查看堆顶的元素是否满足堆的性质，如果不满足，可以将根和左右子节点的值进行比较，取得最大的值交换根元素的值，然后继续考虑被交换的位置。这个过程听起来复杂，但是实施起来并不复杂。

常理，到这里就可以进行编码了，但是这里我还是要继续的多讲一些东西。

堆排序算法和其他基本排序算法比起来，它的构造逻辑也是属于简单逻辑，这种逻辑得益于堆的定义，堆是一个满二叉树，也就是说堆可以使用数组进行表示，结点的父子关系可以通过数组的下标运算所得，另外结点之间的关系，可以简化成父节点和左右子节点的关系，父节点的值只要比左右子节点的值大就可以了，而左右子节点所在的左右子树又可以递归的使用这个性质。最重要的是，堆的调整是不需要进行节点调整的（如果你知道红黑树的实现，就可以体会这句话）。

好了，现在我们可以实现堆排序，代码如下：

package main

import "fmt"

// Heap 定义堆排序过程中使用的堆结构
type Heap struct {
    arr  []int   // 用来存储堆的数据
    size int     // 用来标识堆的大小
}

// adjustHeap 用于调整堆，保持堆的固有性质
func adjustHeap(h Heap, parentNode int) {
    leftNode := parentNode*2 + 1
    rightNode := parentNode*2 + 2

    maxNode := parentNode
    if leftNode < h.size && h.arr[maxNode] < h.arr[leftNode] {
        maxNode = leftNode
    }
    if rightNode < h.size && h.arr[maxNode] < h.arr[rightNode] {
        maxNode = rightNode
    }

    if maxNode != parentNode {
        h.arr[maxNode], h.arr[parentNode] = h.arr[parentNode], h.arr[maxNode]
        adjustHeap(h, maxNode)
    }
}

// createHeap 用于构造一个堆
func createHeap(arr []int) (h Heap) {
    h.arr = arr
    h.size = len(arr)

    for i := h.size / 2; i >= 0; i-- {
        adjustHeap(h, i)
    }
    return
}

// heapSort 使用堆对数组进行排序
func heapSort(arr []int) {
    h := createHeap(arr)

    for h.size > 0 {
        // 将最大的数值调整到堆的末尾
        h.arr[0], h.arr[h.size-1] = h.arr[h.size-1], h.arr[0]
        // 减少堆的长度
        h.size--
        // 由于堆顶元素改变了，而且堆的大小改变了，需要重新调整堆，维持堆的性质
        adjustHeap(h, 0)
    }
}

func main() {
    // 测试代码
    arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    heapSort(arr)
    fmt.Println(arr)
}

最后说一句，程序员想提升自己的编码能力，不仅需要不停的训练，而且还要多多思考。

最后编辑于：2019.03.28 23:04:50