薪酬绩效岗位必备能力(工作能力绩效)
685
2022-05-29
文章目录
前言
堆,是什么?
二叉堆的应用
堆的插入
代码实现
重新看这篇文章
向下调整算法
代码实现(大堆)
向上调整算法
代码实现(大堆)
堆顶元素删除
代码实现
堆排序(大堆)
代码实现
前言
自从写完了上一篇:程序员必备数据结构:栈之后,就一直盘算着写一篇“堆”,今天动手了。
堆,是什么?
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
下图用一个数组来表示堆:
由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。
二叉堆的应用
奈何我比较笨,网上五花八门的介绍,我就看出来三个字:
堆排序
。关于堆的一切应用,也都是基于堆排序的基础上衍生的,所以,本篇不废话,就围绕堆排序展开。
堆的插入
别问我怎么建堆,看完插入,自己去想,反正不是先排序,再建堆。
先看个图:
假设要在这个二叉堆里入队一个单元,键值为2,那么只需在数组末尾加入这个元素,然后尽可能把这个元素往上移动,直到挪不动,经过了这种复杂度O(logn)的操作,二叉堆还是二叉堆。
代码实现
#include
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
重新看这篇文章
在往下看之前,请诸君自行实现上面那个堆的插入与调整,因为我们接下来要进入源码了。
源码之前,了无秘密
向下调整算法
向下调整算法的说明:
*要建一个大堆,即最后每一个堆的节点的值都大于它的孩子
*我们先找左右孩子中最大的一个
*然后让最大的一个孩子和父节点进行比较:
如果孩子大于父节点的值,那么进行交换,并将孩子的值赋给父节点,孩子的值也随父节点的值变化,否则就结束。
*进行向下调整是从根节点开始的,因此,最终的大循环是孩子的值要小于数组存储的元素的值
代码实现(大堆)
//建堆 //建堆所用数组:vector
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
向上调整算法
和向下调整算法很相似
*直接让孩子和父节点进行比较
如果孩子比父节点大的话,就将父亲赋给孩子,然后父亲的值进行改变,一直向上调整,否则结束
*调整结束的另一个结束条件是当调整到最上面的堆顶的时候结束,即就是孩子的值<0
上面那个尾插算法就是个向上调整的。
代码实现(大堆)
//尾插 void Push(const T& x) { _a.push_back(x); _Adjustup(_a.size()-1); } //向上调整 void _Adjustup(int i) { int child = i; int parent = (i-1)/2; while(child >= 0) { if(_a[child] > _a[parent]) { swap(_a[child],_a[parent]); child = parent; parent = (parent-1)/2; } else { break; } } }
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
堆顶元素删除
*先将要删除的堆顶的元素和最后一个元素进行交换
*然后删除尾部的元素
*再进行向下调整
代码实现
//尾删 void Pop() { swap(_a[0],_a[_a.size()-1]); _a.pop_back(); _Adjustdown(0); }
1
2
3
4
5
6
7
堆排序(大堆)
*如果我们是升序的话,要建大堆
*将第一个元素和最后一个元素进行交换,然后进行向下调整
*然后循环第二步,知道堆里剩一个元素,结束
代码实现
#include
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
85
86
87
开发者 数据结构
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。