堆排序

堆排序

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

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

如下图:

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

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

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

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

  • i/2是它的前继节点

    算法原理

    堆排序的算法原理:

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

  • 把堆首(最大值)和堆尾互换.

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

  • 重复步骤2,直到堆的尺寸为 1.Heap Sort

堆排序算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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)
}

运行结果:

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

堆排序
https://www.chendujin.com/posts/c2a5fdc5.html
作者
托马斯
发布于
2022年5月14日
许可协议