在正式开始学习堆之前，一定要先复习一下自己脑中什么是完全二叉树，因为它和堆是息息相关的！如果二叉树中除叶子节点外每个节点的度数均为2，则称该二叉树为满二叉树。而如果除最后一层节点之外的二叉树是一棵满二叉树，并且最后一层的节点从左到右依次分布，则称这棵二叉树为完全二叉树。所以满二叉树一定是完全二叉树。如果你对完全二叉树还不了解，可以看看这篇文章，了解一下Tree的前世今生。对于任意一棵完全二叉树，如果其包含的节点按照层级从左到右进行标记（如上图所示），则对于任意节点i，完全二叉树（二叉堆）满足如下结论：当i>1、父节点是一个节点。当i/2时，当i=1时，表示根节点，无父节点）；例如节点45的标签为4，其父节点15的标签为2，则2=4/2；如果2Xi>n（汇总点数），则该节点一定没有左孩子（对于叶节点）；否则，它的左孩子是节点2Xi。例如，节点15的标签为2，其左子节点为4；如果2X+1>n，则节点i一定没有右孩子；否则，右孩子是节点2Xi+1。堆是一种基于完全二叉树的特殊数据结构。堆通常分为两种类型：最大堆：在最大堆中，根节点的值必须大于其子节点的值，对二叉树中的所有子树也应递归满足。一个特点。小顶堆（MinHeap）：在小顶堆中，根节点的值必须小于其子节点的值，对二叉树的所有子树递归满足相同的性质。不是所有的人都是上过正规课的计算机出身的朋友，所以我说的是概念。小顶堆以任意一个结点为根，它的左右孩子都必须大于等于该结点的值，所以整棵树的根结点一定是树中值最小的结点，而大顶堆的特点恰恰相反。二叉堆二叉堆是满足以下属性的二叉树：二叉堆必须是完全二叉树。二叉堆的这个特性也决定了它们适合用数组存储。二叉堆是小顶堆或大顶堆。小顶二叉堆中根节点的值为整棵树中的最小值，二叉树中的所有顶点及其子树都满足这一性质。大顶堆类似于小顶堆。大顶堆根节点的值是整棵树中的最大值，二叉树中所有节点的值也都大于等于它的子树节点。由于小顶堆和大顶堆除了顶点的大小关系不一致外，都是一棵完全二叉树。下面的所有解释都将以小顶堆为例进行解释。你可以自己写。这是两个典型的小顶桩。二叉堆存储结构二叉堆是一棵完全二叉树，一般用数组表示。根元素用arr[0]表示，其他节点（第i个节点的存储位置）满足下表中的特征：数组表示意思数组表示意思arr[(i-1)/2]i-th节点i的父节点arr[2*i+1]，左子节点arr[2*i+2]i节点的右子节点，二叉堆的这种表示和属性本质上是与完全二叉树本身的属性一一对应。小顶二叉堆常用操作获取小顶二叉堆的根元素getMin()。该操作的时间复杂度为；根据上面的存储结构，根节点为arr[0]，直接返回即可。intgetMin(){returnarr[0];}取出小顶二叉堆的最小元素removeMin()，这个操作的时间复杂度为，因为小顶二叉堆的最小元素（即堆顶元素)被移除之后，需要对堆进行调整，使堆仍然保持其属性。一般调整过程称为heapify。intremoveMin(){if(heap_size<=0)returnINT_MAX;if(heap_size==1){heap_size--;returnharr[0];}//存放最小值（当前堆顶元素），最后一个在heap将元素放在堆顶，然后执行Heapify()introot=harr[0];harr[0]=harr[heap_size-1];heap_size--;MinHeapify(0);returnroot;}取下图为例进行说明：删除栈顶元素10，然后将最后一个元素50作为小顶堆的堆顶：然后从栈顶元素50开始堆。第一步：计算当前堆顶元素50（i=0）的左孩子和右孩子，然后比较三者，选择三者中的最小值，15，交换15和50，继续查值50顶点（i=1）的子树被堆：第二步：计算节点50（i=1）当前要堆的左右孩子，左孩子和右孩子不存在，比较50和45，求50>45，交换两者，然后继续堆值为50的顶点(i=3)的子树：第三步：计算节点50(i=1)待堆，发现不存在，所以节点50已经到了叶子节点，整棵树都堆了下面继续影响！）。更新给定下标updateKey(inti,intnew_val)的值，这里假设new_val
