堆是一种非常常见的数据结构，在计算机操作系统和应用软件中有非常广泛的应用。堆的一个非常典型的应用就是：优先队列。我们平时所理解的普通队列是先进先出，是以时间为标准的。而优先队列则和时间没有关系， 是和每个元素的优先级有关系的。也就是说，在元素出列的时候，是看元素优先级的，优先级高的元素先被处理。那什么样的典型场景会使用优先队列呢？比如：操作系统的任务处理，游戏中某个英雄智能选择攻击的堆象等，都会使用到优先队列。

在这两个场景中，有两个关键点需要理解，一个是当处理完一个优先级高的元素之后，队列中有可能会加入一些新的元素；另一个是队列中旧的元素优先级很有可能会发生变化。这个时候，根据我们以往的经验，需要这个队列重新进行一次优先级的排序。这个排序的过程叫做：动态数据管理。而用堆这个数据结构实现优先队列动态数据管理，是目前最常用的解决方案。

通过上面的两个典型场景我们可以看出来，堆的第一个元素必须是优先级最高的元素，所以篇文章我们重点介绍的就是对应这些场景的，关于堆的一个非常典型的结构实现——最大堆。顾名思义，最大堆的意思就是第一个元素永远是最大的那个元素，不管是插入操作还是删除操作，都要保证第一个元素是最大的元素。所以，我主要会从3个方面来讲解最大堆：最大堆的基本存储方式、最大堆的shiftUp操作，以及最大堆的shiftDown操作。

最大堆的基本存储

如果您有一些关于算法和数据结构的基础常识，您应该能够想到，最大堆的存储结构是一棵树。我们研究的最大堆，是一棵完全二叉树。完全二叉树是指树的第一层至倒数第二层的节点都是满的，倒数第二层的节点如果没有子节点，这些倒数第二层的节点必须是连续没有子节点，而且第一个没有子节点的必须在左边。如下图所示：

堆的数据结构

从上图也可以看出来，最大堆的另一个特点就是：父节点比它的两个子节点的值都要大，最大堆就是由此而来。

对于如何存储一棵树，您的第一反应肯定是建一个链表，然后有左指针和右指针分别指向两个孩子。但，由于最大堆是一个完全二叉树，我们可以根据完全二叉树的特点，使用数组存储一个完全二叉树。具体的存储方式如下图所示：

堆的存储方式

从上图每个节点的序号您应该可以看出来，父节点和子节点之间数学关系是很明显的——左孩子是父节点的序号乘以2，右孩子是父节点的序号乘以2再加1。而父节点的序号则是子节点的序号除以2（计算机除法是直接取整，不要余数）。所以我们可以根据这个数学关系，将树中所有的节点存储到一个数组中，而且关键的是，我们要从下标为1的位置开始计数。

最大堆的shiftUp操作

当我们向一个最大堆中插入一个元素的时候，我们是把元素放到数组的末尾，即保证这棵树还是一个完全二叉树。然后执行shiftUp操作，shiftUp的操作则是保证这棵完全二叉树中的所有父节点还是比它的子节点要大。具体的操作过程如下图所示：

shiftUp

最大堆的shiftDown操作

当我们删除最大对中的元素时，我们必须是删除最大堆的根节点，然后再把最大对的最后一个元素放到根节点上。此时这还是一个完全二叉树，但不能保证所有的父节点都还比它的子节点大。所以，我们要使用shiftDown操作，让最大对再次满足这个性质，具体的操作过程如下图所示：

shiftDown

当我们删除最大堆的根节点时，我们如果一直删除，直到最大堆为空，这个时候，元素的出堆顺序正好是一个降序数列。其实这就是最大堆的排序性质，具体的排序过程和优化的排序技术，我将在下一篇文章中详细介绍。希望这篇文章对你理解最大堆能有所帮助。

我是徐建航，这是我写的第58篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。