堆排序基本知识

基本介绍

堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤:(具体说明看代码注释)

  1. 建堆,循环将数组中的每个数加入堆中(每次都需要heapInsert)
  2. 不断从堆的最后一个元素交换到堆的头部,然后将堆的长度减小1,再调整堆,每次都需要heapify

具体实现

查看代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
func HeapSort(nums []int) []int {
heapSort(nums)
return nums
}

func heapSort(nums []int) {
if nums == nil || len(nums) < 2 {
return
}

//建立堆的过程
for i := 0; i < len(nums); i++ {
heapInsert(nums, i)
}
log.Println("建堆完成--------------->", nums)
heapSize := len(nums)

//之后不断吐出元素
for heapSize > 0 {
nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
heapSize--
heapify(nums, heapSize, 0)
}
}

//用于新加入一个元素之后,向上调整堆
//第2个参数表示新加入的元素的下标
//这个过程的时间复杂度为O(N) = O(log1 + log2 + ... + logN) 近似等于 O(N)
func heapInsert(nums []int, index int) {
//这里左神说了不用加循环结束条件,因为最终的结束条件就是index为0的时候
//因为-1/2也为0
for nums[(index-1)/2] < nums[index] {
nums[index], nums[(index-1)>>1] = nums[(index-1)>>1], nums[index]
index = (index - 1) >> 1
}
}

//左老师的写法

//
//func heapify(nums []int, heapSize int, index int) {
//
// left := 2*index + 1
// for left < heapSize {
// larger := left
// //首先找到左右孩子中最大的
// if left+1 < heapSize && nums[left] < nums[left+1] {
// larger++
// }
//
// //这里要注意一下,如果使用一个变量这里可能会溢出,这里我们使用的larger经过了前面的验证
// if nums[larger] <= nums[index] {
// break
// }
//
// nums[index], nums[larger] = nums[larger], nums[index]
// index = larger
// left = index*2 + 1
// }
//}

//用于将堆顶的元素和堆中最后一个元素交换之后,向下调整堆
//第2个参数为堆的实际大小,因为nums是存放一个数组,
//第3个参数表示该位置元素变动,导致该元素可能要往下沉
//真正的堆是从0->heapSize-1
func heapify(nums []int, heapSize int, index int) {

//注意循环条件
for i := index; i*2+1 < heapSize; {
left := 2*i + 1
//如果有右并且右比左大
if left+1 < heapSize && nums[left+1] > nums[left] {
left++
}

//与左右中较大的比较
if nums[i] >= nums[left] {
break
}

nums[i], nums[left] = nums[left], nums[i]
i = left
}
}

评论