Go 数据结构之堆排序示例详解
什么是堆?
堆(Heap)是一种特殊的树形数据结构,它满足下列性质:
- 堆中每个节点的关键字都不大于(或不小于)其子节点的关键字。
- 堆中,根节点(顶端)是最小或最大元素。
堆实际上是一个完全二叉树,因此可以用数组实现。对于下标为i的节点,其左子节点为2i,右子节点为2i+1,父节点为i/2。
堆分为最大堆和最小堆。在最大堆中,父节点的值大于子节点的值;在最小堆中,父节点的值小于子节点的值。
堆的时间复杂度为O(logN)。
堆排序的过程
堆排序是利用堆进行排序的方法。排序过程分为两个步骤:建立堆和排序。
建立堆
建立堆的过程是将无序的数组构建成一个堆。这个过程可以使用自下而上的方法从最后一个节点开始构建,由于堆中不存在孙子节点,因此可以忽略孙子节点的排列。
示例一:
func buildHeap(arr []int) {
n := len(arr)
for i := n / 2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
}
func heapify(arr []int, n, i int) {
max := i // 找到父节点、左节点、右节点中的最大值
l, r := 2*i+1, 2*i+2
if l < n && arr[l] > arr[max] {
max = l
}
if r < n && arr[r] > arr[max] {
max = r
}
if max != i { // 如果最大值不是父节点,则交换父节点和最大值
arr[i], arr[max] = arr[max], arr[i]
heapify(arr, n, max) // 递归地对最大值所在的子树进行堆化
}
}
在上面的代码中,buildHeap()
函数从最后一个节点的父节点开始进行堆化,调用heapify()
函数进行堆化。
heapify()
函数用于将一个节点及其子树堆化。首先找到父节点、左节点、右节点中的最大值,如果最大值不是父节点,则交换父节点和最大值,并递归地对被交换的子节点进行堆化。
排序
建立好堆之后,进行排序的过程就是将堆顶元素(最小或最大值)与数组的最后一个元素交换,然后将堆的大小减1,并对新的堆顶进行堆化。重复这个过程直到堆的大小为1。
示例二:
func heapSort(arr []int) {
n := len(arr)
buildHeap(arr) // 先建立堆
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0] // 将堆顶元素(最小值)与最后一个元素交换
heapify(arr, i, 0) // 对新的堆顶进行堆化
}
}
在上面的代码中,heapSort()
函数在建立好堆之后,对堆进行排序,在每一次循环中,将堆顶元素与数组的最后一个元素交换,并对新的堆顶进行堆化。
总结
堆排序是一种简单、高效的排序算法。它利用了堆的特点,建立和操作起来都比较容易。在建立堆的过程中,可以选择自下而上的、或自上而下的方法进行堆化。在排序过程中,每次将堆顶元素(最小或最大值)与数组的最后一个元素进行交换,而不必临时占用额外的空间。由于堆的时间复杂度为O(logN),因此堆排序的时间复杂度为O(NlogN)。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Go 数据结构之堆排序示例详解 - Python技术站