程序員必備數(shù)據(jù)結(jié)構(gòu)：堆

文章目錄

前言

堆，是什么？

二叉堆的應(yīng)用

堆的插入

代碼實(shí)現(xiàn)

重新看這篇文章

向下調(diào)整算法

代碼實(shí)現(xiàn)（大堆）

向上調(diào)整算法

代碼實(shí)現(xiàn)（大堆）

堆頂元素刪除

代碼實(shí)現(xiàn)

堆排序（大堆）

代碼實(shí)現(xiàn)

前言

自從寫完了上一篇：程序員必備數(shù)據(jù)結(jié)構(gòu)：棧之后，就一直盤算著寫一篇“堆”，今天動(dòng)手了。

堆，是什么？

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

二叉堆滿足二個(gè)特性：

1．父結(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值。

2．每個(gè)結(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆（都是最大堆或最小堆）。

當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。

下圖用一個(gè)數(shù)組來表示堆：

由于其它幾種堆（二項(xiàng)式堆，斐波納契堆等）用的較少，一般將二叉堆就簡(jiǎn)稱為堆。

二叉堆的應(yīng)用

奈何我比較笨，網(wǎng)上五花八門的介紹，我就看出來三個(gè)字：

堆排序

。關(guān)于堆的一切應(yīng)用，也都是基于堆排序的基礎(chǔ)上衍生的，所以，本篇不廢話，就圍繞堆排序展開。

堆的插入

別問我怎么建堆，看完插入，自己去想，反正不是先排序，再建堆。

先看個(gè)圖：

假設(shè)要在這個(gè)二叉堆里入隊(duì)一個(gè)單元，鍵值為2，那么只需在數(shù)組末尾加入這個(gè)元素，然后盡可能把這個(gè)元素往上移動(dòng)，直到挪不動(dòng)，經(jīng)過了這種復(fù)雜度O（logn）的操作，二叉堆還是二叉堆。

代碼實(shí)現(xiàn)

#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

重新看這篇文章

在往下看之前，請(qǐng)諸君自行實(shí)現(xiàn)上面那個(gè)堆的插入與調(diào)整，因?yàn)槲覀兘酉聛硪M(jìn)入源碼了。

源碼之前，了無秘密

向下調(diào)整算法

向下調(diào)整算法的說明：

*要建一個(gè)大堆，即最后每一個(gè)堆的節(jié)點(diǎn)的值都大于它的孩子

*我們先找左右孩子中最大的一個(gè)

*然后讓最大的一個(gè)孩子和父節(jié)點(diǎn)進(jìn)行比較：

如果孩子大于父節(jié)點(diǎn)的值，那么進(jìn)行交換，并將孩子的值賦給父節(jié)點(diǎn)，孩子的值也隨父節(jié)點(diǎn)的值變化，否則就結(jié)束。

*進(jìn)行向下調(diào)整是從根節(jié)點(diǎn)開始的，因此，最終的大循環(huán)是孩子的值要小于數(shù)組存儲(chǔ)的元素的值

代碼實(shí)現(xiàn)（大堆）

//建堆 //建堆所用數(shù)組：vector _a Heap(T* a, size_t n) :_a(a,a+n) { for(int i = (_a.size()-2)/2; i>=0; i--) { _Adjustdown(i); } } //向下調(diào)整 void _Adjustdown(int root) { int parent = root; int child = parent*2+1; //此處的條件有兩個(gè)： //一個(gè)是當(dāng)孩子的值小于父母的值時(shí)候這個(gè)已經(jīng)在break處理過了 //第二個(gè)條件就是當(dāng)是葉子節(jié)點(diǎn)的時(shí)候 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

向上調(diào)整算法

和向下調(diào)整算法很相似

*直接讓孩子和父節(jié)點(diǎn)進(jìn)行比較

如果孩子比父節(jié)點(diǎn)大的話，就將父親賦給孩子，然后父親的值進(jìn)行改變，一直向上調(diào)整，否則結(jié)束

*調(diào)整結(jié)束的另一個(gè)結(jié)束條件是當(dāng)調(diào)整到最上面的堆頂?shù)臅r(shí)候結(jié)束，即就是孩子的值<0

上面那個(gè)尾插算法就是個(gè)向上調(diào)整的。

代碼實(shí)現(xiàn)（大堆）

//尾插 void Push(const T& x) { _a.push_back(x); _Adjustup(_a.size()-1); } //向上調(diào)整 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

堆頂元素刪除

*先將要?jiǎng)h除的堆頂?shù)脑睾妥詈笠粋€(gè)元素進(jìn)行交換

*然后刪除尾部的元素

*再進(jìn)行向下調(diào)整

代碼實(shí)現(xiàn)

//尾刪 void Pop() { swap(_a[0],_a[_a.size()-1]); _a.pop_back(); _Adjustdown(0); }

1

2

3

4

5

6

7

堆排序（大堆）

*如果我們是升序的話，要建大堆

*將第一個(gè)元素和最后一個(gè)元素進(jìn)行交換，然后進(jìn)行向下調(diào)整

*然后循環(huán)第二步，知道堆里剩一個(gè)元素，結(jié)束

代碼實(shí)現(xiàn)

#include #include using namespace std; template class Heap { public: //構(gòu)造函數(shù) 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: //向下調(diào)整 void _Adjustdown(int root) { int parent = root; int child = parent*2+1; //此處的條件有兩個(gè)： //一個(gè)是當(dāng)孩子的值小于父母的值時(shí)候這個(gè)已經(jīng)在break處理過了 //第二個(gè)條件就是當(dāng)是葉子節(jié)點(diǎn)的時(shí)候 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; } } } //向上調(diào)整 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

開發(fā)者 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。