堆排序

堆排序

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

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

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

堆排序是借助堆数据结构进行排序的一种高效算法,它的平均时间复杂度是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)
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据