1。什么是二叉堆？“二叉树”就不用说了，本章介绍的主要树都是二叉树。那么什么是“堆”呢？在日常生活中，我们通常会说“apileofthings”或“apileofthings”。这里的“堆”通常指的是很多东西相互叠放。我们在堆一堆东西的时候，一定有一个经验，就是为了让这堆东西更稳固，我们会把比较重的大的东西放在下面，轻的小的东西放在上面。这个经验同样适用于数据结构——二叉树。只是“重”和“大”是根据节点值的大小来判断的，是在父节点和子节点之间比较的。例如，取值较大的节点作为子节点；具有较小值的节点被用作父节点。这里举个例子，先看下面的普通二叉树，它也是一棵完全二叉树：再看下面的二叉堆：最小堆这个二叉堆的特点是：它是一棵完全二叉树。二叉堆其实就是由上图的完全二叉树调整改造而成；任一父节点的值小于或等于左孩子和右孩子的值；每个分支从根节点开始。按升序排序（例如分支1-2-3-4）。这样的二叉堆称为最小堆，它的顶端，即根节点A，是整棵树的最小值。最小堆对应的是最大堆：最大堆是一棵完全二叉树；其任一父节点的值大于或等于左孩子和右孩子的值；每个分支从根节点开始。按降序排列。最大堆的堆顶就是整棵树的最大值。我们将上图中的普通二叉树转化为最大堆，如下图所示：最大堆2.二叉堆操作2.1。构造二叉堆给定一棵完整的二叉树，如何调整节点构造二叉堆？下面是一棵无序完全二叉树：现在我们要构造一个最小堆，首先在这棵完全二叉树中找到所有非叶子节点（绿色标记）：我们要做的是：对于每个非叶子节点，做最小堆的“下沉”调整。什么是最小堆的“下沉”调整？对于非叶子节点，如果该节点大于其子节点中最小的一个，则交换两者的位置，否则无需交换。从图中可以看出，非叶子节点（即大值节点）“下沉”了一层。移动是相对的，大值节点的“下沉”就相当于小值节点的“浮”。需要注意的是，有时候下沉一次是不够的，我们需要多次下沉，以保证节点下沉到底（即不再大于其子节点）。所有非叶子节点，从最后一个节点开始，按照从右到左、从下到上的顺序对最小堆进行多次下沉调整，构造一个最小堆。比如一个值为4的非叶子节点，它下沉到第三层后，仍然比它的子节点大。这不是“沉底”，还需要继续沉到第四层。至此，在支路2-4-3-1上，“大值”节点4已经沉底。下面一步步解释：1、对于非叶子节点7，它比它的子节点10小，没有“下沉”；2、对于非叶子节点3，它比其子节点1中较大的节点大，节点3需要“下沉”，与节点1交换，显然节点3已经沉到底部了。3、对于其子节点中比较小的节点5大的非叶子节点6，节点6会“下沉”，与节点5交换位置。显然，节点6已经沉到底部了。4.对于非叶子节点4，它比它的子节点中最小的节点1大，节点4会“下沉”，与节点1交换位置。显然，节点4并没有沉到底部。5、还是对于节点4，它的子节点中比最小的节点3大，节点4会“下沉”，与节点3交换位置，此时节点4已经沉到底部。6、对于非叶子节点2，它比它的子节点中最小的节点1大，节点2会“下沉”，和节点1交换位置，很明显，节点2已经沉到底部了。至此，我们已经将一棵无序的完全二叉树调整转化为一个最小二叉堆。您可以检查最小堆中的所有节点是否满足父节点的值小于子节点的值。此外，所有5个分支都井然有序。构造最大堆的步骤类似，但最大堆的下沉调整是：如果一个结点小于其最大的子结点，则交换两者的位置，出现为非叶子图上的节点（即小值节点）。点）“下沉”一层。通过多次下沉调整，节点不再小于其子节点。下图将无序完全二叉树变成最大堆：2.2.插入节点二叉堆是一棵完全二叉树。向其中插入一个节点，只需将其插入到完全二叉树的最后一个节点的下一个位置即可。例如，要将节点11插入到后面的最大堆中，需要插入到最后一个节点4的下一个位置。当新节点11插入到最大堆中时，它就不再是最大堆了，因为node11破坏了原来堆的结构。因此，我们应该把它看成一棵新的完全二叉树，然后调整新的完全二叉树重新构造最大堆。（调整过程见上）插入过程2.3．删除节点删除操作与插入操作相反。它删除第一个位置的元素，即删除堆顶。我们以删除上图中最大堆的前11个为例。当删除堆的top11时，二叉堆原来的结构就被破坏了，连二叉树都不是了（变成了二叉树）：为了保持完整二叉树的形状，我们加上最后一个将节点7添加到根节点，替换删除的根节点11。这样，我们得到一个新的完全二叉树（不是二叉堆），然后我们可以根据这个新的完全二叉树再次构造最大堆。删除过程3.二叉堆的存储结构二叉堆的存储结构是顺序存储，因为二叉堆是一棵完全二叉树。在【二叉树的存储】一文中我们说：完全二叉树适合顺序存储结构完成。下图是一个最大堆。红色框内为节点编号，与数组下标一一对应。二叉堆的顺序存储链式存储结构可以清晰形象地向我们展示二叉堆中父节点与左右子节点的关系。但是数组中没有指针，只有数组下标，如何表达父子关系呢？其实对于一棵完全二叉树，数组下标就够了！现在假设二叉堆中父节点的数组下标为parent_index，左子数组的下标为left_child_index，右子数组的下标为right_child_index，那么它们之间的关系如下：(1)left_child_index=2×parent_index+1（二）right_child_index=2×parent_index+2（三）parent_index=（left_child_index-1）÷2（四）parent_index=（right_child_index-2）÷2（五）right_child_index=left_child_index+1例如：节点3的下标为3，则其左孩子2的下标为2×3+1=7，右孩子1的下标为2×3+2=8；节点3的下标为3，作为左孩子，其父节点下标为(3-1)÷2=1；该节点7的下标为4，作为右孩子，其父节点下标为(4-2)÷2=1；假设一个节点的数组下标是child_index，你不知道这个节点是左孩子还是右孩子，需要它的父节点的下标，(6)parent_index=(child_index-1)÷2例如：你不知道节点5（下标5）和节点6（下标6）是左孩子还是右孩子，那么节点5和节点6的父节点分别是（5-1）÷2=2和（6-1)÷2=2分别。（注意，编程语言中的整数运算，所以结果不是小数）这里，我们使用结构体来实现二叉堆：#defineMAXSIZE20//数组的最大存储空间typedefstruct{intarray[MAXSIZE];//存储数组intlength;//当前堆长度(节点数)}BinaryHeap;在实际运行之前，需要初始化二叉堆，即分配数组和堆长度：/***@description:Initializethebinaryheap*@param{BinaryHeap}*heapBinaryheap*@param{int}*array数组首地址，数组为无序完全二叉树*@param{int}arr_length数组长度*@return{*}None*/voidinit_heap(BinaryHeap*heap,int*array,intarr_length){//复制数组到heapmemcpy(heap->array,array,arr_length*sizeof(int));//设置堆长度heap->length=arr_length;}4.二叉堆的具体实现4.1。调整和构建这里我们以构建最小堆为例。要构建最小堆，必须调整所有非叶节点。调整的依据是比较非叶节点及其子节点的大小。我们约定parent是一个非叶子节点，parent_index是它的下标。child是它的孩子中较小的一个，child_index是它的下标。child默认开始识别左孩子，那么右孩子的下标为child_index+1。当左孩子小于等于右孩子时，child不需要改变；当左孩子大于右孩子时，需要更新child_index，让child标识右孩子。下面以下图中值为4的非叶子节点为例，说明代码的实现方式。先比较parent的左右孩子，如果左孩子小，那么这个孩子就是左孩子，不需要更新child_index。parent和child在各自的位置，如果发现parent比child大，就可以调换位置。exchange之前，先保存parent的value，即parent_value=4：exchangeposition：先将child的value赋值给parent，从而达到value1上浮的效果：再更新parent_index和child_index，两者都下一级：然后将之前保存的值赋值给当前parent，从而达到值4的下沉效果：一次调整完成，但是对于值4，还没有结束，因为值4还没有沉到底部。此时比较parent的左右孩子，发现右孩子更小，所以孩子是右子树，需要更新child_index让孩子识别右孩子：现在位置可以交换，把child的值赋值给parent，达到3的值。:然后，更新parent_index和child_index的值，两者往下一层：给parent赋值，并到达值4的下沉：此时child_index已经超过了二叉堆的长度，即值4已经到达底部。调整代码如下：/***@description:对某个非叶子节点，进行下沉调整到底部*@param{BinaryHeap}*heap二叉堆（无序）*@param{int}parent_index非叶子节点Node*@return{*}None*/voidadjust_for_min_heap(BinaryHeap*heap,intparent_index){//value保存非叶子节点的值intvalue=heap->array[parent_index];//child_index标识theleftchildintchild_index=parent_index*2+1;//最后一个节点的下标intlast_child_index=heap->length-1;//父节点parent至少有一个childwhile(child_index<=last_child_index){//如果theparentnodeparenthasaleftchildAndtherightchildif(child_index
