数据结构：顺序二叉树（堆）

目次
媒介
一、堆的实现
 1.1 头文件
1.2 堆的初始化及销毁
1.3  堆的插入
1.4 堆的删除
1.5 取堆顶数据和判空

---

媒介

     前面我们讲了二叉树有顺序结构和链式结构，今天就来讲一下顺序结构
       普通的二叉树是不适当用数组来存储的，由于可能会存在大量的空间浪费。而完全二叉树更适当利用顺序结 构存储。现实中我们通常把堆(一种二叉树)利用顺序结构的数组来存储，必要留意的是这里的堆和操作系统 假造进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
  

  一、堆的实现

堆的性质： 堆中某个结点的值总是不大于或不小于其父结点的值，堆总是一棵完全二叉树。

 1.1 头文件

1. #include<stdio.h>
2. #include<assert.h>
3. #include<stdlib.h>
4. #include<stdbool.h>
5. typedef int HPDataType;
6. typedef struct Heap
7. {
8.         HPDataType* a;
9.         int size;
10.         int capacity;
11. }Heap;
13. //堆的初始化
14. void HeapInit(Heap*hp);
15. // 堆的销毁
16. void HeapDestory(Heap* hp);
17. // 堆的插入
18. void HeapPush(Heap* hp, HPDataType x);
19. // 堆的删除
20. void HeapPop(Heap* hp);
21. // 取堆顶的数据
22. HPDataType HeapTop(Heap* hp);
23. // 堆的判空
24. bool HeapEmpty(Heap* hp);

复制代码

    写入我们必要用到的头文件以及堆的底子结构另有用到的堆的功能函数名。
1.2 堆的初始化及销毁

1. void HeapInit(Heap* hp)
2. {
3.         assert(hp);
4.         hp->a = NULL;
5.         hp->size = hp->capacity = 0;
6. }
7. void HeapDestory(Heap* hp)
8. {
9.         assert(hp);
10.         free(hp->a);
11.         hp->a = NULL;
12.         hp->size = hp->capacity = 0;
13. }

复制代码

    这个没什么还说的，就是把数据都置空了。
1.3  堆的插入

1. void HeapPush(Heap* hp, HPDataType x)
2. {
3.         assert(hp);
4.         if (hp->size == hp->capacity)
5.         {
6.                 int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
7.                 HPDataType* tem = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
8.                 hp->capacity = newcapacity;
9.                 hp->a = tem;
10.         }
11.         hp->a[hp->size] = x;
12.         hp->size++;
13.         adjustup(hp->a, hp->size-1);
14. }

复制代码

这里我们会用到向上调整算法 

1. void swap(HPDataType* a, HPDataType* b)
2. {
3.         HPDataType tem = *a;
4.         *a = *b;
5.         *b = tem;
6. }
7. void adjustup(HPDataType* a, HPDataType child)
8. {
9.         int parent = (child - 1) / 2;
10.         while (child > 0)
11.         {
12.                 if (a[parent] > a[child])
13.                 {
14.                         swap(&a[parent], &a[child]);
15.                         child = parent;
16.                         parent = (child - 1) / 2;
17.                 }
18.                 else
19.                 {
20.                         break;
21.                 }
22.         }
23. }

复制代码

     插入数据后要保持父节点比子节点小的性质，要把数据一步步向上调整。
1.4 堆的删除

1. void HeapPop(Heap* hp)
2. {
3.         assert(hp);
4.         swap(&hp->a[0], &hp->a[hp->size - 1]);
5.         hp->size--;
6.         adjustdown(hp->a, hp->size,0);
7. }

复制代码

    删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

1. void adjustdown(HPDataType* a, HPDataType n,HPDataType parent)
2. {
3.         HPDataType child = parent * 2 + 1;
4.         while (child < n)
5.         {
6.                 if (child + 1 < n && a[child + 1] < a[child])
7.                 {
8.                         child++;
9.                 }
10.                 if (a[child] < a[parent])
11.                 {
12.                         swap(&a[child], &a[parent]);
13.                         parent = child;
14.                         child = parent * 2 + 1;
15.                 }
16.                 else
17.                 {
18.                         break;
19.                 }
20.         }
21. }

复制代码

这里给个例子：
       现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个条件：左右子树必须是一个堆，才能调整。
  int array[] = {27,15,19,18,28,34,65,49,25,37};
  

  1.5 取堆顶数据和判空

1. HPDataType HeapTop(Heap* hp)
2. {
3.         return hp->a[0];
4. }

复制代码

    由于是基于数组写的，以是取堆顶就很简朴了。

1. bool HeapEmpty(Heap* hp)
2. {
3.         return hp->size == 0;
4. }

复制代码

    假如数据位空了，那么堆就是空的。
二、完备源码

dui.h

1. #include<stdio.h>
2. #include<assert.h>
3. #include<stdlib.h>
4. #include<stdbool.h>
5. typedef int HPDataType;
6. typedef struct Heap
7. {
8.         HPDataType* a;
9.         int size;
10.         int capacity;
11. }Heap;
14. void HeapInit(Heap*hp);
16. void HeapDestory(Heap* hp);
18. void HeapPush(Heap* hp, HPDataType x);
20. void HeapPop(Heap* hp);
22. HPDataType HeapTop(Heap* hp);
24. int HeapSize(Heap* hp);
26. bool HeapEmpty(Heap* hp);

复制代码

 dui.c

1. #include"dui.h"void HeapInit(Heap* hp)
2. {
3.         assert(hp);
4.         hp->a = NULL;
5.         hp->size = hp->capacity = 0;
6. }
7. void HeapDestory(Heap* hp)
8. {
9.         assert(hp);
10.         free(hp->a);
11.         hp->a = NULL;
12.         hp->size = hp->capacity = 0;
13. }void swap(HPDataType* a, HPDataType* b)
14. {
15.         HPDataType tem = *a;
16.         *a = *b;
17.         *b = tem;
18. }
19. void adjustup(HPDataType* a, HPDataType child)
20. {
21.         int parent = (child - 1) / 2;
22.         while (child > 0)
23.         {
24.                 if (a[parent] > a[child])
25.                 {
26.                         swap(&a[parent], &a[child]);
27.                         child = parent;
28.                         parent = (child - 1) / 2;
29.                 }
30.                 else
31.                 {
32.                         break;
33.                 }
34.         }
35. }void HeapPush(Heap* hp, HPDataType x)
36. {
37.         assert(hp);
38.         if (hp->size == hp->capacity)
39.         {
40.                 int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
41.                 HPDataType* tem = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
42.                 hp->capacity = newcapacity;
43.                 hp->a = tem;
44.         }
45.         hp->a[hp->size] = x;
46.         hp->size++;
47.         adjustup(hp->a, hp->size-1);
48. }void adjustdown(HPDataType* a, HPDataType n,HPDataType parent)
49. {
50.         HPDataType child = parent * 2 + 1;
51.         while (child < n)
52.         {
53.                 if (child + 1 < n && a[child + 1] < a[child])
54.                 {
55.                         child++;
56.                 }
57.                 if (a[child] < a[parent])
58.                 {
59.                         swap(&a[child], &a[parent]);
60.                         parent = child;
61.                         child = parent * 2 + 1;
62.                 }
63.                 else
64.                 {
65.                         break;
66.                 }
67.         }
68. }void HeapPop(Heap* hp)
69. {
70.         assert(hp);
71.         swap(&hp->a[0], &hp->a[hp->size - 1]);
72.         hp->size--;
73.         adjustdown(hp->a, hp->size,0);
74. }HPDataType HeapTop(Heap* hp)
75. {
76.         return hp->a[0];
77. }int HeapSize(Heap* hp){        return hp->size;}bool HeapEmpty(Heap* hp)
78. {
79.         return hp->size == 0;
80. }

复制代码

   
    还是要本身动手写一边才能有印象，写完每个功能点最好一个一个的去测试，这样就不会那么麻烦，更容易知道错哪了，全部写写完再测试，没错误还好说，有错的话，找起来会很痛楚的。

---

     本篇内容就到这里了，盼望对各位有资助，假如有错误欢迎指出。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。