数据结构——二叉树堆的专题

1.堆的概念及结构

如果有一个关键码的集合K = {K0 ，K1 ，K2 ，K3…，K(N-1) }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2*i+1且 Ki<=K2*i+2 ) i = 0，1， 2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

2.堆的性质

（1）堆中某个结点的值总是不大于或不小于其父结点的值； 

（2）堆总是一棵完全二叉树。

3.堆的实现

1.第一种
 

/*向上调整算法（此代码适合大堆）*/
void xiangshang(int *a,int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] < a[child]){int c;c = a[parent];a[parent] = a[child];a[child] = c;}/*else{break;}*/child = parent;parent = (child - 1) / 2;}
}
/*建堆（此代码会建成大堆）*/
void jiandui(int *b,int n)
{for (int i = 0; i < n; i++){xiangshang(b, i);}
}

第一种建堆的具体讲解请看《四种排序方法的补充》 ，里面配有图文讲解，也有向上调整算法与向下调整算法（后面要用到）的图文讲解，希望你可以有耐心的看另一篇文章，希望我的这些讲解对你有用。

C--四种排序方法的补充-CSDN博客

2.第二种

1.创建堆所需要的模型

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

size是确定我开辟的空间中，用掉了多少空间。capacity是确定我开辟了多少个空间。 

2.堆的初始化

/*初始化*/
void Init(HP* ps)
{assert(ps);ps->a = NULL;ps->size = ps->capacity = 0;
}

3.堆的销毁

/*销毁*/
void Destroy(HP* ps)
{assert(ps);free(ps->a);ps->a = NULL;
}

这里要注意的是free（ps->a）之后，free(ps)是错误的操作。不可以销毁ps 

4.插入

/*插入（通过插入会形成大堆）*/
void HeapPush(HP* ps, HPDataType x)
{assert(ps);assert(x);if (ps->capacity == 0){HPDataType* b = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (b == NULL){perror("malloc");exit(0);}ps->capacity = 4;ps->a = b;}if (ps->size == ps->capacity){HPDataType newcapacity = 2 * ps->capacity;HPDataType* b = (HPDataType*)realloc(ps->a, newcapacity * sizeof(HPDataType));if (b == NULL){perror("relloc");exit(0);}ps->a = b;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;xiangshang(ps->a, ps->size - 1);
}

在插入之前我要先判断我是否开辟了空间，然后判断这个空间是否已经被填满。最后再将你所需要的数字放入到最后的位置，通过向上调整算法完成排序。 

 

5.删除元素

/*向下调整算法（此代码适合大堆）*/
void xiangxia(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if ((child + 1) < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){int c;c = a[child];a[child] = a[parent];a[parent] = c;}parent = child;child = parent * 2 + 1;}
}
/*删除元素（此代码在删除元素后还是会形成大堆）*/
void HeapPop(HP* ps)
{assert(ps);assert(ps->size > 0);HPDataType b = ps->a[0];ps->a[0] = ps->a[ps->size - 1];ps->a[ps->size - 1] = b;ps->size--;xiangxia(ps->a, ps->size, 0);
}

删除元素删除的是根的元素，所以我先将根元素与最后的一个元素进行调换位置，然后让size--，（size--是因为下一次插入时，会将那个元素覆盖掉。）最后通过向下调整对这个堆重新排序，（注意：这个代码的前提是这个堆是大堆）让第二个大的坐到根的位置。

6.返还树根元素

/*返回树根元素*/
HPDataType HeapTop(HP* ps)
{assert(ps);assert(ps->size > 0);return ps->a[0];
}

 

7.判断是否为空

/*判断是否为空*/
bool HeapEmpty(HP* ps)
{return ps->size == 0;
}

因为当我初始化之后，size便是0，只有当插入元素之后，size才会大于或等于1。 

8.算多少个

/*算多少个数*/
int HeapSize(HP* ps)
{assert(ps);return ps->size;
}

9.打印树的内容

/*打印树的内容*/
void HeapPrintf(HP* ps,int size)
{int i = 0;for (; i < size; i++){printf("%d ", ps->a[i]);}
}