数据布局：堆

目录

1.堆的概念
2.堆的布局
3.堆的初始化
4.堆的烧毁
5.堆的插入
6.堆的删除
7.判断堆是否为空

---

1.堆的概念

堆的性子：

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

以下堆的布局默认大堆 ：
2.堆的布局

堆是非线性数据布局，相当于一维数组，有两个直接后继 。

1. //大堆
2. typedef int HPDataType;
3. typedef struct Heap
4. {
5.         HPDataType* _a;
6.         int _size;    //数组中元素的个数
7.         int _capacity;  //数组的容量
8. }Heap;

复制代码

堆是怎样存储在数组中呢？
在数组下标中，若当前节点在数组中的下标为 i， 则其父节点的下标为 （i-1）/2，其左子节点的下标为 i*2+1，其右子节点的下标为i*2+1+1；
若一个节点的下标为3，其父节点的小标为1，其左孩子节点的下标为7，右孩子结点的下标为8。
3.堆的初始化

1. /初始化
2. void HeapInit(Heap* php)
3. {
4.         assert(php);
5.         php->_a = (HPDataType*)malloc(sizeof(HPDataType)*5);
6.         php->_size = 0;
7.         php->_capacity = 5;
8. }

复制代码

4.堆的烧毁

1. // 堆的销毁
2. void HeapDestory(Heap* php)
3. {
4.         free(php->_a);
5.         php->_size = 0;
6.         php->_capacity = 0;
7. }

复制代码

5.堆的插入

 首先插入时，判断数组空间是否已满，若满了则扩容，接着在数组的最后举行插入，然后举行向上调整（向上调整就是判断父亲和孩子的大小，若孩子大于父亲则举行交换，）

1. void Swap(HPDataType* p1, HPDataType* p2)
2. {
3.         HPDataType tmp = *p1;
4.         *p1 = *p2;
5.         *p2 = tmp;
6. }
7. void AdjustUp(Heap* php, int child)
8. {
9.         assert(php);
10.   // 找到插入节点的父结点的下标
11.         int parent = (child - 1) / 2;
12.         while (child > 0)
13.         {
14.   //   若孩子结点大于父亲结点，则父亲和孩子进行交换，然后改变父亲结点和孩子结点的下标
15.                 if (php->_a[child] > php->_a[parent])
16.                 {
17.                         Swap(&php->_a[child], &php->_a[parent]);
18.                         child = parent;
19.                         parent = (child - 1) / 2;
20.                 }
21.                 else
22.                 {
23.                         break;
24.                 }
25.         }
26. }
27. // 堆的插入
28. void HeapPush(Heap* php, HPDataType x)
29. {
30.         assert(php);
31.         //扩容
32.         if (php->_size == php->_capacity)
33.         {
34.                 HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity * 2);
35.                 if (tmp == NULL)
36.                 {
37.                         perror("push::realloc");
38.                         return;
39.                 }
40.                 php->_a = tmp;
41.                 php->_capacity *= 2;
42.         }
43.        
44.         php->_a[php->_size] = x;
45.         php->_size++;
46.         //向上调整
47.         //                插入元素的数组下标
48.         AdjustUp(php, php->_size - 1);
49. }

复制代码

6.堆的删除

这里的删除是删除数组中第一个元素（即最大的的元素），首先将数组中最后一个元素和第一个元素举行交换，然后举行向下调整，满足大堆的条件

1. void AdjustDown(Heap* php,int n,int parent)
2. {
3.         assert(php);
4. //找到左孩子
5.         int child = parent * 2 + 1;
6.         while (child < n)
7.         {
8.                 //判断右孩子是否存在， 若存在则将左孩子和右孩子进行比较
9.         // 若右孩子大于左孩子，则将右孩子与父亲作比较，即child++，找到右孩子下标
10.                 if (child + 1 < n && php->_a[child] < php->_a[child + 1])
11.                 {
12.                         child++;
13.                 }
14.                
15.                 //当父母小于孩子时，交换，同时重新赋值父亲结点和孩子结点
16.                 if(php->_a[parent] < php->_a[child])
17.                 {
18.                         Swap(&php->_a[parent], &php->_a[child]);
19.                         parent = child;
20.                         child = parent * 2 + 1;
21.                 }
22.                 else
23.                 {
24.                         break;
25.                 }
26.         }
27. }
28. // 堆的删除
29. void HeapPop(Heap* php)
30. {
31.         assert(php);
32.         assert(!HeapEmpty(php));
33.    //删除头元素
34.         Swap(&php->_a[0], &php->_a[php->_size - 1]);
35.         php->_size--;
36.         //向下调整
37.     //  需要从根节点进行调整
38.         AdjustDown(php,php->_size,0);
39. }

复制代码

7.判断堆是否为空

1. // 堆的判空   空1，非空0
2. int HeapEmpty(Heap* php)
3. {
4.         assert(php);
5.         return php->_size == 0;
6. }

复制代码

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