【百度百科】堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做 一棵完全二叉树的数组对象。
完全二叉树的性质就是堆的性质，堆是完全二叉树的顺序结构存储。
① 堆总是一棵完全二叉树。
② 堆中的某个节点的值总是不大于或不小于其父节点的值。
堆的逻辑结构是完全二叉树，物理（存储）结构是数组
1.完整Heap.h
和以前学的数据结构一样，先定义出堆的结构体，然后实现接口函数。
先给出Heap.h的代码：
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* array; //指向动态开辟的数组 int size; //有效数据的个数 int capacity; //容量空间的大小 } Heap; void HeapInit(Heap* php);//初始化堆 void HeapDestroy(Heap* php);//堆的销毁 void HeapPrint(Heap* php);//堆的打印 bool HeapEmpty(Heap* php);//判断堆是否为空 HPDataType HeapTop(Heap* php);//返回堆顶数据 int HeapSize(Heap* php);//统计堆的个数 void HeapCheckCapacity(Heap* php);//检查容量 void Swap(HPDataType* px, HPDataType* py);//交换函数 void HeapPush(Heap* php, HPDataType x);//堆的插入 void BigAdjustUp(int* arr, int child);//大根堆上调 void SmallAdjustUp(int* arr, int child);//小根堆上调 void HeapPop(Heap* php);//堆的删除 void SmallAdjustDown(int* arr, int n, int parent);//小根堆下调 void BigAdjustDown(int* arr, int n, int parent);//大根堆下调
2.八个简单函数
这八个函数前几篇数据结构文章都讲过类似的了，直接放出来
void HeapInit(Heap* php)//初始化堆 { assert(php); php->array = NULL; php->size = php->capacity = 0; } void HeapDestroy(Heap* php) //堆的销毁 { assert(php); free(php->array); php->capacity = php->size = 0; } void HeapPrint(Heap* php) //堆的打印 { for (int i = 0; i < php->size; i++) { printf("%d ", php->array[i]); } printf("\n"); } bool HeapEmpty(Heap* php)//判断堆是否为空 { assert(php); return php->size == 0; // 如果为size为0则表示堆为空 } HPDataType HeapTop(Heap* php) //返回堆顶数据 { assert(php); assert(!HeapEmpty(php)); return php->array[0]; } int HeapSize(Heap* php) //统计堆的个数 { assert(php); return php->size; } void HeapCheckCapacity(Heap* php) //检查容量 写过很多次了 { if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : (php->capacity * 2); HPDataType* tmpArray = (HPDataType*)realloc(php->array, sizeof(HPDataType) * newCapacity); if (tmpArray == NULL) { printf("realloc failed!\n"); exit(-1); } //更新他们的大小 php->array = tmpArray; php->capacity = newCapacity; } } void Swap(HPDataType* px, HPDataType* py) //交换函数 { HPDataType tmp = *px; *px = *py; *py = tmp; }
3.大堆的插入（HeapPush）
void HeapPush(HP* php, HPDataType x) { assert(php); // 写到这里写一个检查是否需要增容 HeapCheckCapacity(php); // 插入数据 php->array[php->size] = x; php->size++; // 写到这里写一个向上调整 传入目标数组，和插入的数据（即 size - 1）。 AdjustUp(php->array, php->size - 1); }
插入的核心思路：
① 先将元素插入到堆的末尾，即最后一个孩子之后。
② 插入之后如果堆的性质遭到破坏，就将新插入的节点顺着其的父亲往上调整到合适位置。
直到调到符合堆的性质为止。
根据堆的性质，如果不满足大堆和小堆，出现子大于父或父大于子的情况，
为了保证插入之后堆还是堆，我们就需要进行自下往上的调整。
堆插入数据对其他节点没有影响，只是可能会影响从它到根节点路径上节点的关系。
比如下面的情况：新插入的为 60，子大于父（60 > 56 ），这时就需要交换。
先把父亲赋值给孩子，再把孩子赋值给父亲，再让父亲往上走，判断是否比父亲大，如果大就再进行交换。 为了搞定这些情况，我们就需要写一个 "向上调整" 的算法（最坏调到根停止）：
3.1大堆向上调整（BigAdjustUp）
void BigAdjustUp(int* arr, int child) //大根堆上调 { assert(arr); // 首先根据公式计算算出父亲的下标 int parent = (child - 1) / 2; // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0） while (child > 0) //不能写parent >= 0 { //为什么呢？最后一次往上走时， //child = parent; 此时child = 0 //parent = (child - 1) / 2; //(0 - 1) / 2 = 0 这么一来parent仍然会是0 //导致parent根本就不会小于0 if (arr[child] > arr[parent]) // 如果孩子大于父亲（不符合堆的性质） { // 交换他们的值 Swap(&arr[child], &arr[parent]); // 往上走 child = parent; parent = (child - 1) / 2; } else// 如果孩子小于父亲（符合堆的性质） { break;// 跳出循环 } } }
3.2小堆向上调整（SmallAdjustUp）
如果我们想改成小堆向上调整呢？
只需要改变一下大于小于判断条件即可：
void SmallAdjustUp(int* arr, int child) //小堆上调 { assert(arr); // 首先根据公式计算算出父亲的下标 int parent = (child - 1) / 2; // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0） while (child > 0) { if (arr[child] < arr[parent]) // 如果孩子小于父亲（不符合小堆的性质） { Swap(&arr[child], &arr[parent]); // 往上走 child = parent; parent = (child - 1) / 2; } else // 如果孩子小于父亲（符合堆的性质） { break; } } }
4.堆的删除（HeapPop）
因为在讲堆的插入时我们用大堆演示的，我们这里先用小堆来演示。
删除的核心思路：删除堆，删除的是堆顶的数据。就是删除这个树的根。
如果直接挪动数据把堆顶数据覆盖，那么堆的结构就乱了，还要走一遍插入的逻辑，效率太低
所以有人想出一种很巧妙的方法：
将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
（向下调整算法堆排序要使用，使用前提是左子树和右子树都是大堆/小堆）
① 将堆顶元素与堆中最后一个元素进行交换。
② 删除堆中的最后一个元素。
③ 将堆顶元素向下调整到满足堆特性为止。
void HeapPop(HP* php) { assert(php); assert(!HeapIsEmpty(php)); // 删除数据 Swap(&php->array[0], &php->array[php->size - 1]); php->size--; // 写到这里写一个向下调整 传入目标数组，，数组的大小，调整位置的起始位置 SmalljustDown(php->array, php->size, 0); }
4.1小堆向下调整（SmallAdjustDown）
向下调整，把它调整成堆，跟左右孩子中小的那个交换。
结束条件（有一个成立即可）：
① 父<=小的孩子，则停止。
② 调整到叶子（因为叶子特征为没有孩子，左孩子下标超出数组范围，就不存在了）。
//小根堆下调 左右子树为小根堆，根节点不满足时使用 左右子树不满足就对其进行下调 void SmallAdjustDown(int* arr, int n, int parent) { int child = parent * 2 + 1; // 默认为左孩子 while (child < n) // 叶子内 { // 选出左右孩子中小的那一个 if (child + 1 < n && arr[child + 1] < arr[child]) //左孩子+1为右孩子 { //如果 child + 1 比 n 大，就说明没有右孩子，默认是对的 child++;//左孩子+1更新为右孩子 } if (arr[child] < arr[parent])// 如果孩子小于父亲（不符合小堆的性质） { // 交换它们的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else // 如果孩子大于父亲（符合小堆的性质） { break; } } }
如果我们想改成大堆呢？
也只需要改变一下大于小于判断条件即可：
① 选出左右孩子大的那一个。
② 小堆是所有父亲都小于孩子，大堆则是所有父亲都要大于孩子，我们来改一下：
4.2大堆向下调整（BigAdjustDown）
void BigAdjustDown(int* arr, int n, int parent) //大堆下调 { int child = parent * 2 + 1; // 默认为左孩子 while (child < n) { // 叶子内 // 选出左右孩子中大的那一个 if (child + 1 < n && arr[child + 1] > arr[child]) { child++; } if (arr[child] > arr[parent]) // 如果孩子大于父亲（不符合大堆的性质） { // 交换它们的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else // 如果孩子小于父亲（符合大堆的性质） { break; } } }
5.堆的构建完整代码
Heap.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* array; //指向动态开辟的数组 int size; //有效数据的个数 int capacity; //容量空间的大小 } Heap; void HeapInit(Heap* php);//初始化堆 void HeapDestroy(Heap* php);//堆的销毁 void HeapPrint(Heap* php);//堆的打印 bool HeapEmpty(Heap* php);//判断堆是否为空 HPDataType HeapTop(Heap* php);//返回堆顶数据 int HeapSize(Heap* php);//统计堆的个数 void HeapCheckCapacity(Heap* php);//检查容量 void Swap(HPDataType* px, HPDataType* py);//交换函数 void HeapPush(Heap* php, HPDataType x);//堆的插入 void BigAdjustUp(int* arr, int child);//大根堆上调 void SmallAdjustUp(int* arr, int child);//小根堆上调 void HeapPop(Heap* php);//堆的删除 void SmallAdjustDown(int* arr, int n, int parent);//小根堆下调 void BigAdjustDown(int* arr, int n, int parent);//大根堆下调
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" void HeapInit(Heap* php)//初始化堆 { assert(php); php->array = NULL; php->size = php->capacity = 0; } void HeapDestroy(Heap* php) //堆的销毁 { assert(php); free(php->array); php->capacity = php->size = 0; } void HeapPrint(Heap* php) //堆的打印 { for (int i = 0; i < php->size; i++) { printf("%d ", php->array[i]); } printf("\n"); } bool HeapEmpty(Heap* php)//判断堆是否为空 { assert(php); return php->size == 0; // 如果为size为0则表示堆为空 } HPDataType HeapTop(Heap* php) //返回堆顶数据 { assert(php); assert(!HeapEmpty(php)); return php->array[0]; } int HeapSize(Heap* php) //统计堆的个数 { assert(php); return php->size; } void HeapCheckCapacity(Heap* php) //检查容量 写过很多次了 { if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : (php->capacity * 2); //第一次给4，其他情况扩2倍 HPDataType* tmpArray = (HPDataType*)realloc(php->array, sizeof(HPDataType) * newCapacity); // 数组扩容 if (tmpArray == NULL) { //检查realloc printf("realloc failed!\n"); exit(-1); } //更新他们的大小 php->array = tmpArray; php->capacity = newCapacity; } } void Swap(HPDataType* px, HPDataType* py) //交换函数 { HPDataType tmp = *px; *px = *py; *py = tmp; } void BigAdjustUp(int* arr, int child) //大根堆上调 { assert(arr); // 首先根据公式计算算出父亲的下标 int parent = (child - 1) / 2; // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0） while (child > 0) //不能写parent >= 0 { //为什么呢？最后一次往上走时， //child = parent; 此时child = 0 //parent = (child - 1) / 2; //(0 - 1) / 2 = 0 这么一来parent仍然会是0 //导致parent根本就不会小于0 if (arr[child] > arr[parent]) // 如果孩子大于父亲（不符合大堆的性质） { // 交换他们的值 Swap(&arr[child], &arr[parent]); // 往上走 child = parent; parent = (child - 1) / 2; } else// 如果孩子小于父亲（符合堆的性质） { break;// 跳出循环 } } } void SmallAdjustUp(int* arr, int child) //小堆上调 { assert(arr); // 首先根据公式计算算出父亲的下标 int parent = (child - 1) / 2; // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0） while (child > 0) { if (arr[child] < arr[parent]) // 如果孩子小于父亲（不符合小堆的性质） { Swap(&arr[child], &arr[parent]); // 往上走 child = parent; parent = (child - 1) / 2; } else // 如果孩子小于父亲（符合堆的性质） { break; } } } void HeapPush(Heap* php, HPDataType x) { assert(php); // 检查是否需要扩容 HeapCheckCapacity(php); // 插入数据 php->array[php->size] = x; php->size++; // 向上调整 [目标数组，调整位置的起始位置（刚插入的数据）] BigAdjustUp(php->array, php->size - 1); } //小根堆下调 左右子树为小根堆，根节点不满足时使用 左右子树不满足就对其进行下调 void SmallAdjustDown(int* arr, int n, int parent) { int child = parent * 2 + 1; // 默认为左孩子 while (child < n) // 叶子内 { // 选出左右孩子中小的那一个 if (child + 1 < n && arr[child + 1] < arr[child]) //左孩子+1为右孩子 { //如果 child + 1 比 n 大，就说明没有右孩子，默认是对的 child++;//左孩子+1更新为右孩子 } if (arr[child] < arr[parent])// 如果孩子小于父亲（不符合小堆的性质） { // 交换它们的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else // 如果孩子大于父亲（符合小堆的性质） { break; } } } void BigAdjustDown(int* arr, int n, int parent) //大根堆下调 { int child = parent * 2 + 1; // 默认为左孩子 while (child < n) // 叶子内 { // 选出左右孩子中大的那一个 if (child + 1 < n && arr[child + 1] > arr[child]) { child++; } if (arr[child] > arr[parent]) { // 如果孩子大于父亲（不符合大堆的性质） // 交换它们的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else // 如果孩子小于父亲（符合大堆的性质） { break; } } } void HeapPop(Heap* php) { assert(php); assert(!HeapEmpty(php)); // 删除数据 Swap(&php->array[0], &php->array[php->size - 1]); php->size--; // 向下调整 [目标数组，数组的大小，调整位置的起始位置] //SmallAdjustDown(php->array, php->size, 0); BigAdjustDown(php->array, php->size, 0); }
Test.c
#include"Heap.h" int main() { Heap h; HeapInit(&h); int arr[] = { 15,18,19,25,34,28,65,27,49,37 }; for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++) { HeapPush(&h, arr[i]); } HeapPrint(&h); HeapPop(&h); HeapPrint(&h); HeapPush(&h, 100); HeapPush(&h, 40); HeapPrint(&h); HeapPop(&h); HeapPrint(&h); return 0; }
