堆的介绍，实现（c语言实现）

堆的概念

堆的性质：

堆的分类

父子结点的下标关系

堆的向下调整算法

编辑小堆

大堆

建堆

堆的向上调整算法

小堆

大堆

堆的基本操作

定义堆

初始化堆

销毁堆

打印堆

堆的插入

堆的删除

大堆（Max Heap）的向下调整算法思路：

小堆（Min Heap）的向下调整算法思路：

关键点解释：

获取堆的数据个数

堆的判空

堆的概念

如果有一个关键码的集合K = { k1，k2 ，k3 ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：i = 0，1， 2…，则称为小堆(或大堆)。

在数据结构中，堆（Heap）是一种特殊的树形数据结构，通常被实现为完全二叉树或近似完全二叉树。堆的一个重要特性是它满足堆属性，即每个节点的值都大于或等于（在最大堆中）或小于或等于（在最小堆中）其子节点的值。

堆在计算机科学中有广泛的应用，尤其是在实现优先队列和堆排序算法中。优先队列是一种数据结构，其中元素的优先级决定了它们的出队顺序。堆可以作为一种高效的优先队列实现方式，因为堆顶元素总是优先级最高（最大或最小）的元素。堆排序算法则利用堆的性质，通过构建最大堆或最小堆，并反复取出堆顶元素来实现排序。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

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

堆的分类

堆主要分为两种类型：最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，父节点的值总是大于或等于其子节点的值，因此堆顶元素是整个堆中的最大值。相反，在最小堆中，父节点的值总是小于或等于其子节点的值，堆顶元素是整个堆中的最小值。

堆通常使用数组来实现，数组中的每个元素对应堆中的一个节点。由于堆是完全二叉树，所以可以使用数组的下标关系来模拟树中父节点和子节点之间的关系。这种实现方式使得堆在插入、删除和查找最大（或最小）元素等操作中具有高效的性能。

父子结点的下标关系

在堆的数据结构中，我们通常将数组中的每个元素视为一个结点，这些结点按照完全二叉树的顺序存储在数组中。每个结点都有一个唯一的下标，通过下标关系，我们可以确定任意结点的父结点和子结点的位置。

对于给定下标 i 的结点，其父结点、左子结点和右子结点的下标可以通过以下关系式计算：

下标i元素的父结点下标：(i - 1) / 2（使用整数除法）
下标i元素的左子结点下标：2 * i + 1
下标i元素的右子结点下标：2 * i + 2

这些关系式基于完全二叉树的性质。在完全二叉树中，除了最后一层，其他层的结点是满的，且最后一层的结点都靠左对齐。因此，对于任意结点，其左子结点的下标是其下标的两倍加一，右子结点的下标是其下标的两倍加二，而父结点的下标则是通过将其下标减一后除以二（整数除法）得到。

通过这些下标关系，我们可以方便地在数组中进行堆的操作，如插入、删除、堆化等。例如，在插入新元素时，我们可以将其放在数组的末尾，并通过与其父结点比较和交换（如果需要）来维护堆的性质。同样地，在删除堆顶元素时，我们可以将数组的最后一个元素移动到堆顶，并通过与其子结点比较和交换来重新调整堆。

需要注意的是，当使用这些下标关系时，我们需要确保下标不会超出数组的范围。例如，根结点的下标为 0，它没有父结点。对于任意结点，我们需要检查其左子结点和右子结点的下标是否超出了数组的长度，以避免访问不存在的元素。

通过使用结点和下标关系，我们可以高效地实现堆的数据结构，并利用其特性进行各种操作，如快速找到最大（或最小）元素、插入新元素、删除元素等。

堆的向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

但是，使用向下调整算法需要满足一个前提：

若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

小堆

向下调整算法的基本思想（以建小堆为例）：

从根结点处开始，选出左右孩子中值较小的孩子。
让小的孩子与其父亲进行比较。

（1）若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
（2）若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{//child记录左右孩子中值较小的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小{child++;//较小的孩子改为右孩子}if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换Swap(&a[child], &a[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}
}

大堆

向下调整算法的基本思想（以建大堆为例）如下：

从根结点处开始，选出左右孩子中值较大的孩子。
让较大的孩子与其父亲进行比较。

若较大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来较大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。

若较大的孩子比父亲小或者没有孩子（即已经是叶子结点），则不需处理了，调整完成，整个树已经是大堆了。

//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//堆的向下调整（大堆）  
void AdjustDown(HPDataType* a, int n, int parent)  
{  int child = parent * 2 + 1; // 计算左子节点的索引  // 当 child 索引在数组范围内时执行循环  while (child < n)  {  // 如果右子节点存在且大于左子节点  if (child + 1 < n && a[child+1] > a[child])  {  ++child; // 更新 child 为右子节点的索引  }  // 如果 child 节点（现在是左右子节点中较大的一个）大于 parent 节点  if (a[child] > a[parent])  {  Swap(&a[child], &a[parent]); // 交换 parent 和 child 的值  parent = child; // 更新 parent 为刚刚交换过的 child 的索引  child = parent * 2 + 1; // 重新计算左子节点的索引  }  else  {  break; // child 节点不大于 parent 节点，无需继续调整，退出循环  }  }  
}

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而 $h=log_{2}(n+1)$ （N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。

建堆

上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？

答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

代码

	//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(php->a, php->size, i);}

那么建堆的时间复杂度又是多少呢？
当结点数无穷大时，因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

所以T(n)=O(N)

总结一下：
堆的向下调整算法的时间复杂度：T(n)=O(logN)。
建堆的时间复杂度：T(n)=O(N)。

堆的向上调整算法

当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法。

小堆

向上调整算法的基本思想（以建小堆为例）：

将目标结点与其父结点比较。
若目标结点的值比其父结点的值小，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。
若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了。

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}//堆的向上调整（小堆）
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//调整到根结点的位置截止{if (a[child] < a[parent])//孩子结点的值小于父结点的值{//将父结点与孩子结点交换Swap(&a[child], &a[parent]);//继续向上进行调整child = parent;parent = (child - 1) / 2;}else//已成堆{break;}}
}

大堆

向上调整算法的基本思想（以建大堆为例）如下：

将目标结点与其父结点比较。
若目标结点的值大于其父结点的值，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。
若目标结点的值不大于其父结点的值，则停止向上调整，此时该树已经是大堆了。

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}// 除了child这个位置，前面数据构成堆
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while(child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

堆的基本操作

定义堆

typedef int HPDataType;//堆中存储数据的类型typedef struct Heap
{HPDataType* a;//用于存储数据的数组int size;//记录堆中已有元素个数int capacity;//记录堆的容量
}HP;

初始化堆

然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{assert(php);HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构if (tmp == NULL){printf("malloc fail\n");exit(-1);}php->a = tmp;memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中php->size = n;php->capacity = n;int i = 0;//建堆for (i = (php->size - 1 - 1) / 2; i >= 0; i--){AdjustDown(php->a, php->size, i);}
}

当然还有简化的版本

void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}

销毁堆

为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。

//销毁堆
void HeapDestroy(HP* php)
{assert(php);free(php->a);//释放动态开辟的数组php->a = NULL;//及时置空php->size = 0;//元素个数置0php->capacity = 0;//容量置0
}

打印堆

打印堆中的数据，这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印，即打印成树形结构。

//求结点数为n的二叉树的深度
int depth(int n)
{assert(n >= 0);if (n>0){int m = 2;int hight = 1;while (m < n + 1){m *= 2;hight++;}return hight;}else{return 0;}
}//打印堆
void HeapPrint(HP* php)
{assert(php);//按照物理结构进行打印int i = 0;for (i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");//按照树形结构进行打印int h = depth(php->size);int N = (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数int space = N - 1;//记录每一行前面的空格数int row = 1;//当前打印的行数int pos = 0;//待打印数据的下标while (1){//打印前面的空格int i = 0;for (i = 0; i < space; i++){printf(" ");}//打印数据和间距int count = (int)pow(2, row - 1);//每一行的数字个数while (count--)//打印一行{printf("%02d", php->a[pos++]);//打印数据if (pos >= php->size)//数据打印完毕{printf("\n");return;}int distance = (space + 1) * 2;//两个数之间的空格数while (distance--)//打印两个数之间的空格{printf(" ");}}printf("\n");row++;space = space / 2 - 1;}
}

堆的插入

数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

这个插入的效果完全取决于AdjustUp函数是给大堆设计的还是小堆！！

堆的删除

堆的向下调整算法思路主要涉及到在删除堆顶元素（最大或最小元素）后，从堆的最后一个元素开始，将其放到堆顶，并通过一系列的交换操作来重新维护堆的性质。这个算法在堆排序和优先队列等应用中非常关键。

大堆（Max Heap）的向下调整算法思路：

准备阶段：
- 假设堆中当前有 n 个元素，删除堆顶元素后，将最后一个元素（第 n 个元素）移动到堆顶位置。
- 初始化当前节点 k 为堆顶节点（索引为 0 或 1，取决于实现）。
调整过程：
- 获取当前节点 k 的左右子节点的索引。
- 比较当前节点 k 的值与左右子节点的值，找到三者中的最大值。
- 如果最大值不是当前节点 k，则将其与最大值所在位置的节点交换。
- 更新 k 为交换后的最大值所在位置的节点索引。
- 重复上述步骤，直到 k 没有子节点或者 k 的值不小于其子节点的值，此时堆的性质得以恢复。

小堆（Min Heap）的向下调整算法思路：

准备阶段：
- 与大堆类似，删除堆顶元素后，将最后一个元素移动到堆顶位置。
- 初始化当前节点 k 为堆顶节点。
调整过程：
- 获取当前节点 k 的左右子节点的索引。
- 比较当前节点 k 的值与左右子节点的值，找到三者中的最小值。
- 如果最小值不是当前节点 k，则将其与最小值所在位置的节点交换。
- 更新 k 为交换后的最小值所在位置的节点索引。
- 重复上述步骤，直到 k 没有子节点或者 k 的值不大于其子节点的值，此时堆的性质得以恢复。

关键点解释：

子节点索引：对于数组实现的堆，可以通过 (k * 2 + 1) 和 (k * 2 + 2) 来获取当前节点 k 的左子节点和右子节点的索引（假设数组下标从 0 开始）。
比较与交换：根据堆的性质（大堆或小堆），比较当前节点与其子节点的值，并根据需要进行交换，以保证堆的性质得以维持。
终止条件：当当前节点 k 没有子节点（即 k 的索引超过了数组长度的一半减一），或者当前节点的值已经满足堆的性质（对于大堆是不小于子节点，对于小堆是不大于子节点）时，算法终止。

通过这种向下调整算法，可以在删除堆顶元素后快速恢复堆的性质，使得堆能够继续作为有效的数据结构进行后续操作。

//堆的删除
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置php->size--;//删除最后一个结点（也就是删除原来堆顶的元素）AdjustDown(php->a, php->size, 0);//向下调整
}

获取堆的数据个数

获取堆的数据个数，即返回堆结构体中的size变量。

//获取堆中数据个数
int HeapSize(HP* php)
{assert(php);return php->size;//返回堆中数据个数
}

堆的判空

堆的判空，即判断堆结构体中的size变量是否为0。

//堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;//判断堆中数据是否为0
}