[数据结构——lesson10.堆及堆的调整算法]

引言

上节我们学习完二叉树后[数据结构——lesson9.二叉树]，这节我们将学习数据结构——堆

学习目标

1.堆的概念及结构

堆是一种特殊的完全二叉树结构，在计算机科学和数据结构中广泛应用，特别是在堆排序算法和优先队列的实现中，堆可以通过数组来表示，这种表示方式利用了完全二叉树的性质，即除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。

1.1堆的概念

堆通常是一个可以被看作一棵完全二叉树的数组对象，若满足：

(1)任意节点的值>=其子节点的值。则称为大根堆。

(2)任意节点的值<=其子节点的值。则称为小根堆。

1.2堆的结构

逻辑结构：堆是一棵完全二叉树，除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。
物理结构：堆在物理上通常采用顺序存储，即使用数组来表示。根节点位于数组的第一个位置（下标通常为 0 或 1）。对于下标从 1 开始的数组，任意节点 i 的左子节点为 2i，右子节点为 2i+1；对于下标从 0 开始的数组，左子节点为 2i+1，右子节点为 2i+2。通过这种方式，可以利用数组的随机访问特性高效地模拟树的结构。

如图所示：

操作系统和数据结构这两门学科中都有栈和堆的概念，如何区分 ❓

数据结构角度

栈：是一种运算受限的线性表2。只允许在表的一端进行插入和删除操作，遵循后进先出（LIFO）原则。主要操作有入栈（Push）和出栈（Pop）。可使用数组或链表作为底层数据结构，分别称为顺序栈和链式栈。
堆：是一种特殊的树形数据结构。通常可分为最大堆和最小堆，最大堆中父节点的值大于等于子节点的值，最小堆中父节点的值小于等于子节点的值。主要操作包括插入元素和删除堆顶元素等，并需重新调整堆的结构。常用于实现优先队列、堆排序等。

操作系统角度

栈：是进程地址空间中的一块区域，用于存储函数调用时的局部变量、函数参数和返回地址等信息。其内存由操作系统自动分配和释放，函数调用时压栈，函数返回时弹栈。栈的大小有限，一般每个进程的栈大小相对较小，如 64 位 Linux 系统默认栈大小通常为 10MB。内存地址生长方向是从高地址向低地址增长。
堆：也是进程地址空间中的一部分，用于动态内存分配。程序运行时通过 malloc 或 new 等函数分配内存，大小可变。内存由程序员手动管理，需调用相应函数释放内存，否则易引发内存泄漏。堆的内存地址通常从低地址向高地址增长，由于是通过分散的内存块管理，其内存空间在物理上不连续，频繁操作可能产生内存碎片。

二者联系

1.3堆的调整算法

在实现堆的结构之前我们先要了解一下堆的调整算法

1.堆的数值交换

思路：堆的交换还是比较简单的，跟之前写的没什么区别，记得传地址。
void swap(HPDatatype* x, HPDatatype* y)
{int temp = 0;temp = *x;*x = *y;*y = temp;
}
2.堆的向上调整算法 （应用于堆的数据插入）

此算法是为了确保插入数据后的堆依然是符合堆的性质而单独封装出来的函数，就好比如我们后续要插入的数字10（小堆）

基本思路：将新增元素插入到堆数组的末尾，然后将该元素与其父结点进行比较。若该元素的值小于父结点的值（小根堆）或大于父结点的值（大根堆），则交换两者的位置，之后将原父结点当作新的目标结点，继续向上进行比较和交换操作，直到该元素的值不小于父结点的值（小根堆）或不大于父结点的值（大根堆），或者到达根节点为止。

为了确保在插入数字10后依然是个小根堆，所以要将10和28交换，依次比较父结点parent和子结点child的大小，当父小于子结点的时候，就返回，反之就一直交换，直到根部while(child>0)截止。

：由前文的得知的规律，parent = (child - 1) / 2，我们操控的是数组，但要把它想象成二叉树。画图演示调整过程：

代码实现：
// 向上调整函数（没有改变动态数组的首地址，不需要用指针传输）
// 时间复杂度O(logN)
// 传入了 动态数组  和  最后一个位置的下标（也就是孩子的下标）
// 向上调整的条件；上面的数据是堆
void AdjustUp(HPDatatype* a, int child)
{// 计算父亲的小标int parent = (child - 1) / 2;// 当 child 的小标大于 0 就继续 （也就小于是根节点位置）while (child > 0){// 小堆 <// 大堆 >if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
核心逻辑：

计算父节点下标：parent = (child - 1) / 2
循环比较子节点与父节点的值
如果子节点值小于父节点值（符合小堆特性），则交换两者位置
更新子节点和父节点下标，继续向上比较
当子节点成为根节点（child > 0不成立）或满足堆特性时，循环结束

3.堆的向下调整算法（应用于堆的数据删除）

此算法是为了确保删除数据后的堆依然是符合堆的性质而单独封装出来的函数，就好比如我们后续要删除数字10（小堆）

基本思路：首先将堆顶元素与堆中最后一个元素进行交换，然后删除最后一个元素（此时堆顶元素为原来的堆尾元素）。接着从堆顶开始，将堆顶元素与它的子节点进行比较，如果子节点中有比它更小（小根堆）或更大（大根堆）的元素，则将堆顶元素与该子节点交换位置，之后继续以交换后的位置为新的 “堆顶”，重复上述比较和交换操作，直到满足堆的性质为止。

如下图：

（我们这里首先将堆顶元素（10）与堆中最后一个元素进行交换（28），然后删除最后一个元素（10））

此时我们看到，这个二叉树整体上不符合堆的性质，但是其根部的左子树和右子树均满足堆的性质。接下来，就要进行向下调整，确保其最终是个堆。只需三部曲。

▶：找出左右孩子中最小的那个

▶：跟父亲比较，如果比父亲小，就交换

▶：再从交换的孩子位置继续往下调整

代码实现：
// 向下调整
// 向下调整的前提：后面的数据是堆
void AdjustDown(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]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
核心逻辑：

先计算左孩子下标：child = parent * 2 + 1
循环条件：孩子下标小于总元素个数（未超出边界）
首先判断是否存在右孩子，并且比较左右孩子大小，选择较小的那个孩子（小堆特性）
比较父节点与选中的孩子节点值，如果孩子值更小，则交换两者位置
更新父节点和孩子节点下标，继续向下比较
当父节点满足堆特性或没有孩子节点时，循环结束

2.堆的实现方式

虽然堆是一种特殊的二叉树，它既可以用数组存储也可以用链式存储。但是考虑到其完全二叉树的特性，我们在这里采用数组存储的方式，因为这样既方便访问，也并不会浪费格外的空间。

数组与堆的映射关系(这里实现根的下标为0)：

1.若某节点在数组中的下标为i（i从0开始），则其左子节点(若存在)的下标为2i+1，右子节点（若存在）的下标为2i+2，其父节点（若存在）的下标为（i-1）/2。

2.堆的根节点在数组的下标为0。

2.1堆的声明

由于我们使用数组来实现堆，因此堆的声明与顺序表类似。