一、堆的概念
堆是一种顺序存储完全二叉树的数据结构。
二、堆的一些性质
堆分为小堆和大堆：
小堆要求父亲结点数据小于孩子结点；
大堆要求父亲结点数据小于孩子结点。
如何根据孩子结点下标找到父亲结点？
parent = (child - 1) / 2
如何根据父亲结点下标找到孩子结点？
child = 2 * parent + 1 （左孩子）
三、堆的结构定义
堆的结构中包含数组、堆大小、堆容量
//堆的结构定义 typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP;
四、堆的初始化
将数组初始化为空，堆大小和容量都初始化为0
//堆的初始化 void HPInit(HP* php) { php->a = NULL; php->size = 0; php->capacity = 0; }
五、堆打印
打印数组
//堆打印 void HPPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); }
六、向上调整算法
孩子结点与父亲结点比较，如果孩子结点小于父亲结点，就将孩子结点与父亲结点交换。
注意第二个循环条件：是 child > 0，为什么不是 parent >=0 呢？
因为parent最小是0，永远不会小于0。但是该代码也能跑，因为当parent为0时，重置下标时，child重置为0，而parent = (child - 1) / 2也重置为0，此时a[child] = a[parent]，因此循环结束。
//向上调整算法 void AdjustUp(HPDataType*a, int child) { int parent = (child - 1) / 2; while (a[child] < a[parent] && child > 0)//孩子结点比父亲结点小 { //交换父亲结点和孩子结点的数据 HPDataType tmp = a[child]; a[child] = a[parent]; a[parent] = tmp; //父亲结点和孩子结点下标重置 child = parent; parent = (child - 1) / 2; } }
七、堆的插入
插入数据前先检查堆容量是否足够，容量不够则扩容，容量足够则将数据存入数组中，再用向上调整算法将新插入的数据进行调整。
//堆的插入 void HPPush(HP* php, HPDataType x) { assert(php); //堆扩容 if (php->size ==php->capacity ) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->size++] = x; //向上调整算法 AdjustUp(php->a, php->size - 1); }
八、向下调整算法
将父亲结点与孩子结点比较，如果父亲结点大于孩子结点，则交换
由于可能有两个孩子结点，先要确认右孩子是否存在，如果存在取较小的孩子结点与父亲结点交换
//向下调整算法 void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size)//存在右孩子 { if (a[child + 1] < a[child])//右孩子比左孩子小，用右孩子顶替父亲结点位置 { child = child + 1; } } if (a[child] < a[parent]) { //交换父亲结点与孩子结点 HPDataType tmp = a[child]; a[child] = a[parent]; a[parent] = tmp; //重置父亲结点和孩子结点 parent = child; child = parent * 2 + 1; } else { break; } } }
九、堆的删除
堆的删除是删除堆顶元素，因为删除堆尾元素是没有意义的。
删除堆顶即删除二叉树的根，删除后还要使之成为一个完全二叉树，所以需要用次小值去顶替堆顶的位置。
具体方法：
先将堆尾元素与堆顶元素交换位置，然后删除堆尾元素，再利用向下调整算法将堆顶位置元素向下调整到合适的位置。
//堆的删除 void HPPop(HP* php) { assert(php); assert(php->size);//空堆不可删除 //交换堆顶元素和堆底元素 HPDataType tmp = php->a[0]; php->a[0] = php->a[php->size - 1]; php->a[php->size - 1] = tmp; //删除堆底元素 php->size--; //向下调整算法 AdjustDown(php->a, php->size, 0); }
十、取堆顶元素
先判断堆是否为空，不空则返回堆顶元素
//取堆顶元素 HPDataType HPTop(HP* php) { assert(php); assert(php->size); return php->a[0]; }
十一、求堆大小
返回size即可
//求堆大小 size_t HPSize(HP* php) { assert(php); return php->size; }
十二、堆判空
利用size判断堆是否为空
//判空 bool HPEmpty(HP* php) { assert(php); return php->size == 0; }
十三、测试代码
void test01() { //创建堆 HP hp; //初始化堆 HPInit(&hp); //堆插入 HPPush(&hp, 1); HPPush(&hp, 5); HPPush(&hp, 3); HPPush(&hp, 6); HPPush(&hp, 7); HPPush(&hp, 5); HPPush(&hp, 4); HPPush(&hp, 9); HPPush(&hp, 8); //堆打印 HPPrint(&hp); //堆插入 HPPush(&hp, 1); //堆打印 HPPrint(&hp); //堆删除 HPPop(&hp); //堆打印 HPPrint(&hp); //取堆顶元素 printf("%d\n", HPTop(&hp)); //求堆大小 printf("%zd\n", HPSize(&hp)); //堆判空 if (HPEmpty(&hp)) printf("空\n"); else printf("非空\n"); } int main() { test01(); return 0; }
