程序员必备数据结构:堆

网友投稿 685 2022-05-29

文章目录

前言

堆,是什么?

二叉堆的应用

堆的插入

代码实现

重新看这篇文章

向下调整算法

代码实现(大堆)

向上调整算法

代码实现(大堆)

堆顶元素删除

代码实现

堆排序(大堆)

代码实现

前言

自从写完了上一篇:程序员必备数据结构:栈之后,就一直盘算着写一篇“堆”,今天动手了。

堆,是什么?

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性:

1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

下图用一个数组来表示堆:

由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

二叉堆的应用

奈何我比较笨,网上五花八门的介绍,我就看出来三个字:

堆排序

。关于堆的一切应用,也都是基于堆排序的基础上衍生的,所以,本篇不废话,就围绕堆排序展开。

堆的插入

别问我怎么建堆,看完插入,自己去想,反正不是先排序,再建堆。

先看个图:

假设要在这个二叉堆里入队一个单元,键值为2,那么只需在数组末尾加入这个元素,然后尽可能把这个元素往上移动,直到挪不动,经过了这种复杂度O(logn)的操作,二叉堆还是二叉堆。

代码实现

#include #include using namespace std; void push_heap(vector& vec, int num) { vec.push_back(num); int sz = vec.size()-1; int parent = sz / 2 - 1; while (vec[sz] < vec[parent]) { vec[sz] ^= vec[parent]; vec[parent] ^= vec[sz]; vec[sz] ^= vec[parent]; sz = parent; parent /= 2; } } int main() { vector vec = {1,3,5,11,4,6,7,12,15,10,9,8}; push_heap(vec,2); for (int i = 0; i < 13; i++) { cout << vec[i]<<" "; } cout << endl; return 0; }

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 _a Heap(T* a, size_t n) :_a(a,a+n) { for(int i = (_a.size()-2)/2; i>=0; i--) { _Adjustdown(i); } } //向下调整 void _Adjustdown(int root) { int parent = root; int child = parent*2+1; //此处的条件有两个: //一个是当孩子的值小于父母的值时候这个已经在break处理过了 //第二个条件就是当是叶子节点的时候 while(child<_a.size()) { //找左右孩子中值最大的 if(child+1<_a.size() && _a[child+1]>_a[child]) { ++child; } //将孩子和父母做比较 if(_a[child]>_a[parent]) { swap(_a[child],_a[parent]); parent = child; child = parent*2+1; } 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

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 #include using namespace std; template class Heap { public: //构造函数 Heap() {} //建堆 Heap(T* a, size_t n) :_a(a,a+n) { for(int i = (_a.size()-2)/2; i>=0; i--) { _Adjustdown(i); } } //堆排 void HeapSort() { //升序,建大堆 for(int i = (_a.size()-2)/2; i>=0; --i) { _Adjustdown(i); } int end = _a.size()-1; while(end>0) { swap(_a[0],_a[_a.size()-1]); _Adjustdown(end); --end; } } protected: //向下调整 void _Adjustdown(int root) { int parent = root; int child = parent*2+1; //此处的条件有两个: //一个是当孩子的值小于父母的值时候这个已经在break处理过了 //第二个条件就是当是叶子节点的时候 while(child<_a.size()) { //找左右孩子中值最大的 if(child+1<_a.size() && _a[child+1]>_a[child]) { ++child; } //将孩子和父母做比较 if(_a[child]>_a[parent]) { swap(_a[child],_a[parent]); parent = child; child = parent*2+1; } else { break; } } } //向上调整 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; } } } protected: vector _a; };

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小时内删除侵权内容。

上一篇:解密TaurusDB存储端高并发之线程池
下一篇:Linux系统编程-进程间通信(管道)
相关文章