什么是堆？堆其实就是一个特殊的队列——优先级队列。普通的队列游戏规则很简单：先进先出；但是这种优先级队列比较特殊，不是按照入队的先后顺序，而是按照每个元素的优先级来竞争的，优先级最高的在堆顶。这也很好理解。比如各种软件都有会员制，某款软件可以通过使用会员来加快下载速度。不同等级的入会速度是不同的，也就是优先级不同。其实大家回微信也是默默的把消息放到一堆里，按顺序排列：先回复男女朋友，再回复其他人。这与操作系统中的“堆”不同。这两个虽然叫堆，但其实并没有什么关系。他们都借用了英文单词Heap。我们再回顾一下“堆”在整个Java集合框架中的位置：即PriorityQueue是一个类（class）；PriorityQueue继承自Queue接口（Interface）；堆在哪里？堆其实是一个抽象的数据结构，或者说是逻辑数据结构，并不是物理上真实的数据结构。堆的实现方式其实有很多种，比如二项式堆，斐波那契堆等等。但是面试中考的最多的，也是最经典的，就是二叉堆binaryheap，它是用完全二叉树实现的。完全二叉树是如何实现的？其实是用数组实现的！所以二叉堆/PriorityQueue其实是用数组来实现的。这个数组的排列方式有点特殊，因为它会一直把你定义的（或者默认的）优先级最高的元素保持在数组的第一位，所以并不是随便什么数组都叫“堆”，其实，它在你心里，应该是一棵“完全二叉树”。这棵完整的二叉树只存在于你的心里，存在于各种书籍中；其实在记忆中，哪有什么树？它只是一个数组。那么为什么完全二叉树可以用数组来实现呢？所有的树都可以用数组来实现吗？这就涉及到了完全二叉树的性质。我们将在下一篇文章中详细介绍。简单的说，因为完全二叉树的定义要求层序遍历时没有气泡，也就是连续存储，所以可以用数组存储；第二个问题当然是是否是。堆的特点1.堆是一棵完全二叉树；2.堆序（heaporder）：任何节点都优于它的所有子节点。A。如果任何节点都大于它的所有子节点，这样的堆就称为大顶堆，MaxHeap；b.如果任何一个结点都小于它所有的孩子，这样的堆称为小顶堆，左图MinHeap就是小顶堆，可以看出对于每个结点，它都小于它的所有孩子。注意所有的孩子，包括孙子，曾孙...3.由于堆是用数组实现的，我们可以找到每个节点和它的父/子节点的关系，允许直接访问它们。比如对于节点3，它的Index=1，它的parentindex=0，leftchildleftchildindex=3，rightchildrightchildindex=4。可以总结出如下规则：设置当前节点的indexnode=x,那么parentindex=(x-1)/2,leftchildleftchildindex=2*x+1,rightchildrightchildindex=2*x+2.有些书可能写的略有不同，因为他们arrays是从1开始的，我这里的数组下标是从0开始的，都是可以的。这样就可以从任意一点一步找到它的孙子和曾孙。确实很方便，后面说具体操作的时候大家可以更深入的理解。任何数据结构的基本操作无非就是增删改查四大类：函数方法时间复杂度addoffer(Ee)O(logn)deletepoll()O(logn)没有直接APIdelete+addcheckpeek()O(1)这里peek()的时间复杂度很好理解，因为堆的目的是快速得到一组数据中的最大/最小值，所以这一步的时间复杂度一定是O(1)是的，这就是堆的用途。那我们具体看一下offer(Ee)和poll()的过程。offer(Ee)比如我们刚才在最小堆上新加了一个0：很明显0应该放在最上面，但是直接放在上面就不是完全二叉树了。.因此，我们首先保证树在添加元素后仍然是一颗完全二叉树，然后通过swap对其进行微调以满足堆序。这样就保证了堆的两个特性都满足，即保证加入新元素后还是堆。那么具体怎么做呢：第一步，把0放在最后，先接上，不要一上来就想上位；好的！我们终于先落地了，然后我们再一步一步往上走。这里“能不能上去”的标准是：是否满足堆序。也就是说，现在堆序在5和0之间不满足，然后交换位置，直到满足堆序。这里最小堆的堆序是小数必须在最上面。Step2.和5交换，此时0和3不满足堆序，再交换。Step3.和3交换不够，0还是小于1，所以继续交换。第4步。交换1OK！这样一个新的堆就诞生了~总结一下这个方法：先把新的元素添加到数组的末尾，然后通过不断比较这个值和父值来决定是否交换。直到满足堆顺序。这个过程就是siftUp()，源码如下：时间复杂度在这里不难发现。事实上，我们只交换了一个分支上的元素，也就是最多O(height)次。那么对于一棵完全二叉树，除了最后一层是满的，O(height)=O(logn)。所以offer(Ee)的时间复杂度是O(logn)。poll()poll()就是把最顶层的元素拿走。顺便说一句，没有办法把中间的元素去掉。毕竟要人先出去，小弟才能出去。然后最顶层的元素拿走后，这个位置是空的：首先要满足堆叠顺序，因为比较容易满足，就从最下面拿一个来填满，先放一个木偶上去。步骤1。最后一个元素放在上面的位置。这样堆序又不满足了，交换元素。那么8比7和3大，我应该和谁交换呢？假设和7交换，那么7还是比3大，7和3还得交换，麻烦。所以它与左右孩子中较小的一个交换。Step2.和3交换后，还是比5和4大，再和4交换。步骤3.用4交换OK！这棵树终于稳了。总结一下这个方法：先把数组的最后一个元素加到最顶部，然后通过不断比较左右孩子的值，直到满足堆序，来判断是否交换。这个过程就是siftDown()，源码如下：时间复杂度相同，只交换一个分支上的元素，即最多O(height)次。所以offer(Ee)的时间复杂度是O(logn)。Heapify()还有一个众所周知的非常重要的操作，就是heapify()。可以在O(n)时间内将一个乱序的数组变成堆，这是一个非常神奇的操作。但是，heapify()不是公共API，请参阅：所以我们无法直接使用它。唯一使用heapify()的方法是在使用PriorityQueue(Collectionc)构造函数时，人们会自动调用heapify()操作。你是怎么做到的？哈哈源码暴露了：从最后一个非叶子节点开始，从后往前做siftDown()。因为不需要操作叶子节点，已经到了底部，和谁交换呢？?例如：我们要对这个数组进行heapify()，将其变成一个最小堆，得到它的最小值。然后从3开始，分别对3、7、5进行siftDown()。Step1.尴尬😅，3不需要交换，因为以它为顶点的小树已经满足堆序了。步骤2.7比它的两个孩子都大，所以它与较小的孩子交换。兑换完成后；Step3.最后要处理的是5，这里5比它的两个孩子都大，所以也和小的交换。替换后结果如下。注意堆序不满足，因为4还是小于5。于是再改成4，结果如下：这样，整个heapify()过程就完成了。那么，困难来了。为什么时间复杂度是O(n)？如何计算这个时间复杂度？其实我们在这个过程中所做的操作无非就是交换和交换。那你交换了多少次？没错，你交换了多少次，时间复杂度是一样的。那么我们可以看到，其实同层节点的最大交换次数是一样的。那么总的交换次数=每层节点数*每个节点最大交换数这里k是层数，那么本例中k=3。所以heapify()的时间复杂度是O(n)。以上就是对堆的三个重要操作，虽然最后一个heapify()不能直接操作，但是在堆排序中使用了这种思路。其中一些在之前的文章“选择排序”中也有提到。有兴趣的同学可以在后台回复“选择排序”获取文章~至于堆排序的具体实现和应用，以及为什么没有在实际生产中使用，后面再说。最后说一下有点题外话，最近发现几篇文章把我的文章搬到了其他平台，每篇文章都是我精心制作的，都是我自己的宝贝，看到别人直接搬运，不注明作者和出处，实在是太难受了。。。为了最好的阅读体验，文中的图片我都没有加水印，不过这样也方便别人携带。今天三思而后行，还是不想违背初衷，毕竟我的读者比较重要，以后有朋友看到请后台或微信告知，万分感谢！本文转载自微信公众号“码农田小七”，可以关注以下二维码。转载阅读本文请联系码农田小七公众号。
