数据结构与算法：堆

朋友们大家好啊，本篇文章来到堆的内容，堆是一种完全二叉树，再介绍堆之前，我们首先对树进行讲解

1.树的介绍

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，n=0时成为空树，当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。

• 有一个特殊的结点，称为根结点（A），根节点没有前驱结点。n>0 时根结点是唯一的，不可能存在多个根节点
• 每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

这两种情况就是错误的

1.1节点的分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图所示，这棵树结点的度的最大值是结点D的度为3，所以树的度为3

结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。

结点的层次（Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根就在第L+1层。其双亲在同一层的结点互为堂兄弟。显然 D、E、F是堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度，当前树的深度为4。

2.树的存储结构

提到存储结构，我们会想到两种：顺序存储和链式存储
先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的

树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系，你想想看，数据元素挨个的存储，谁是谁的双亲，谁是谁的孩子呢?简单的顺序存储结构是不能满足树的实现要求的。

树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

其中data是数据域，firstchild为指针域，存储该结点的第一个孩子结点的存储地址,rightsib是指针域，存储该结点的右兄弟结点的存储地址。

typedef int DataType;
struct Node
{struct Node* firstchild; // 第一个孩子结点struct Node* rightsib; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

3.二叉树的概念和结构

二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

3.1 二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有五种基本情况：

3.2 特殊的二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。一个树的层数为K，且节点总数为2^k-1，则它就是满二叉树
  单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。

• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉树的特点：

• (1)叶子结点只能出现在最下两层。
• (2)最下层的叶子一定集中在左部连续位置。
• (3)倒数二层，若有叶子结点，一定都在右部连续位置
• (4)如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
• (5)同样结点数的二叉树,完全二叉树的深度最小

完全二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1 个结点
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n₀，度为2的分支结点个数为n₂，则有n₀＝n₂＋1
4. 具有n个节点的完全二叉树的深度为[log₂n]+1

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
5. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
6. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
7. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

3.3二叉树的存储结构

前面我们已经谈到了树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等

将这棵二叉树存入到数组中,相应的下标对应其同样的位置


考虑一种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2^k一1个存储单元空间，这显然是对存储空间的浪费，如图:

所以，顺序存储结构一般只用于完全二叉树

4.堆的介绍和实现

堆是一棵完全二叉树，堆中的每一个节点都满足堆性质，也就是每个节点的值都必须大于（或等于）或小于（或等于）其子节点的值。根据这个性质，堆可以分为两种类型：

• 大堆：在大堆中，每个父节点的值都大于或等于其子节点的值。因此，堆的根节点（即堆顶）包含了堆中的最大值。
• 小堆：在小堆中，每个父节点的值都小于或等于其子节点的值。因此，堆的根节点包含了堆中的最小值。

下面是一个小堆的结构：

       1/   \3     6/ \   / \5  9  8   13

在这个小堆中：

• 根节点1是最小的元素。
• 每个子节点3, 6的值都大于等于它们的父节点1的值。
• 这个性质适用于堆的所有层：例如，节点5, 9, 8, 13的值都大于等于它们各自的父节点3, 6的值。

这个小堆对应数组存储结构为1 3 6 5 9 8 13

下面是一个大堆的结构：

       13/    \9      8/ \    / \5  3   6   1

对应数组结构为13 9 8 5 3 6 1

堆的树形结构只是一种抽象的概念，在实际的物理存储上，堆通常是以数组的形式来实现的

4.1 堆的实现，初始化与销毁

堆的成立是数组数据不断调整的过程，这里我们创建出堆的框架：

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

初始化

void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

初始化堆数据数组的指针为 NULL。这意味着堆开始时没有分配任何内存用于存储元素。通常，在第一次向堆中添加元素时，程序会根据需要分配内存

销毁

void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->size = 0;php->capacity = 0;
}

free 函数释放堆结构中动态分配的数组 a 所占用的内存。php->a 是指向堆中元素数组的指针，在堆初始化或元素添加过程中，会通过 malloc、realloc 等动态内存分配函数分配内存。释放这块内存是防止内存泄露的重要步骤。释放后，这块内存不应再被访问

4.2插入元素与向上调整

void HeapPush(Heap* 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->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;Ajustup(php->a, php->size - 1);
}

首先判断php不为空，再进行扩容，这个扩容在前面有多次提到
最主要的是下面的Ajustup函数

4.2.1堆向上调整

我们这里以小堆为例进行讲解：

当向堆中插入一个新元素后，为了维持小顶堆的性质（即父节点的值始终小于等于其子节点的值），可能需要进行元素的向上调整）。下面详细说明这个过程：

1. 当一个新元素被加入到堆中时，它首先被放置在堆的末尾（即作为树的最底层的最右侧的叶子节点），以保持完全二叉树的形状。
2. 比较新节点与其父节点的值：插入的新元素可能会破坏小顶堆的性质，此时需要将新元素与其父节点进行比较。对于数组中的节点 i（假设索引从0开始），其父节点的位置是 (i - 1) / 2。注意这里全是整数值，比如下标为2的元素，它的父节点就为0
3. 如果新元素的值小于其父节点的值，那么就需要交换这两个节点的值，因为在小顶堆中父节点应当是小于或等于子节点的值
4. 向上递归：继续将现在的节点位置（原父节点的位置，因为已经交换）与新的父节点进行比较，如果还是小新的父节点的值，继续交换。这一过程一直进行，直到新元素到达根节点，或新元素大于或等于其父节点的值。

接下来我们用函数实现

void Ajustup(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 = (parent - 1) / 2;}elsebreak;}
}

• 对于给定的子节点索引child，其父节点的索引计算为(child - 1) / 2
• 循环条件：while (child > 0)循环确保我们不会尝试移动根节点（因为根节点的索引为0，没有父节点）。循环继续执行，只要当前节点的索引大于0。
• 完成交换后，更新child变量为原父节点的索引，因为交换后当前元素已经移动到了父节点的位置。然后，对新的child值重新计算parent索引，继绀执行可能的进一步交换
• 循环终止条件：如果当前节点的值不小于其父节点的值（即堆的性质得到了满足），循环终止，else break;执行

补充Swap函数：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2; *p2 = tmp;
}

有了这个调整函数，我们就可以建堆了

4.2.2堆的建立

通过调用Ajustup函数，逐步把输入数组a转换成一个小堆

我们在主函数中进行测试

这个经验证确实是一个小堆

4.2.3 堆元素的删除和向下调整

堆默认规定，要删除根节点的数据

堆顶存放最小值，删除后，为了满足小堆的性质，接下来根节点存储的为次小值

• 由于堆是以数组的形式存储的，堆顶元素就是数组的第一个元素。删除堆顶元素后，需要保持堆的完整性和顺序特性

• 将堆的最后一个元素移动到堆顶：为了保持结构性质，堆的最后一个元素被移动到堆顶位置。这是因为在二叉堆中，我们希望维护一个完全二叉树的结构。使用最后一个元素来替代被删除的元素是一种简单且有效的方法，它保证了树的结构完整性。

• 移动最后一个元素到堆顶后，这个新的堆顶元素可能会破坏堆的顺序性质。为了恢复堆的性质，需要执行下沉操作。具体步骤如下：

  • 比较新的堆顶元素与其子节点。
  • 如果在最小堆中，新的堆顶元素比其子节点大，则它需要与其最小的子节点交换位置； 在最大堆中，如果新的堆顶元素比其子节点小，则它需要与其最大的子节点交换位置。
  • 重复这个比较和交换过程，直至新的堆顶元素被移至正确的位置，也就是说，它不再比任何一个子节点大（在最小堆中）或小（在最大堆中）

void HeapPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;Ajustdown(php->a,php->size,0);
}

向下调整函数

void Ajustdown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child<size){if (child + 1 < size && a[child + 1] < a[child])//防止只有左孩子而越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}

我们需要找小一点的孩子进行交换

1. 子节点选择：计算左子节点的索引（child = parent * 2 + 1）。在二叉堆中，给定父节点索引为i的情况下，左子节点的索引为2*i + 1，右子节点的索引为2*i + 2。开始时，我们先考虑左子节点。
2. while循环：确保当前考虑的子节点索引没有超出数组的界限，如果有两个节点，判断右节点是否小于左节点，如果小，child++，后面让右孩子与父节点交换
3. 更新parent索引为当前child的索引，继续向下遍历堆。更新child索引为新parent索引的左子节点，准备进行下一轮的比较。
4. 结束循环：如果子节点的值不小于父节点的值，说明当前父节点的位置适当，堆的性质得以维持，此时循环可以终止。

对于每次AdjustDown调用，最坏情况下需要进行的比较和交换次数与堆的高度成正比，即O(log n)

AdjustDown操作的时间复杂度是O(log n)

4.3 获取堆顶元素与堆的数据个数

HPDataType HeapTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

int HeapSize(Heap* php)
{assert(php);return php->size;
}

4.4判断堆是否为空

bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

如果是空，返回true，不是则返回false

本节内容到此结束，感谢大家观看！！！