数据结构秘籍（四） 堆 （详细包含用途、分类、存储、操作等）

1 引言 

什么是堆？

堆是一种满足以下条件的树：（树这一篇可以参考我的文章数据结构秘籍（三）树 （含二叉树的分类、存储和定义）-CSDN博客）

堆中的每一个结点值都大于等于（或小于等于）子树中所有结点的值。

很多博客说堆是完全二叉树，其实并非如此，堆不一定是完全二叉树，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆，事实上，广为人知的斐波那契堆和二项堆就不是完全二叉树,它们甚至都不是二叉树。
• （二叉）堆是一个数组，它可以被看成是一个 近似的完全二叉树。——《算法导论》第三版

判断一下下面给出的图是否是堆

 第1 个和第 2 个是堆。第 1 个是最大堆，每个节点都比子树中所有节点大。第 2 个是最小堆，每个节点都比子树中所有节点小。第3个不是，在第三个中，有的结点比子结点小，有的比子结点大不符合堆的特性。

2 堆的用途

当我们只关心所有数据中的最大值或者最小值，存在多次获取最大值或者最小值，多次插入或删除数据时，就可以使用堆。

对比有序数组而言，初始化一个有序数组时间复杂度是 O(nlog(n))，查找最大值或者最小值时间复杂度都是 O(1)，但是，涉及到更新（插入或删除）数据时，时间复杂度为 O(n)，即使是使用复杂度为 O(log(n)) 的二分法找到要插入或者删除的数据，在移动数据时也需要 O(n) 的时间复杂度。

相对于有序数组而言，堆的主要优势在于插入和删除数据效率较高。 因为堆是基于完全二叉树实现的，所以在插入和删除数据时，只需要在二叉树中上下移动节点，时间复杂度为O(log(n))，相比有序数组的 O(n)，效率更高。

不过，需要注意的是：Heap 初始化的时间复杂度为 O(n)，而非O(nlogn)。

3 堆的分类

堆分为最大堆和最小堆。二者的区别在于结点的排序方式。

• 最大堆：堆中的每一个结点的值都大于等于子树中所有结点的值。
• 最小堆：堆中的每一个结点的值都小于等于子树中所有结点的值。

在下图中，图1是最大堆，图2是最小堆。

4 堆的存储

之前介绍树的时候说过，由于完全二叉树的优秀性质，利用数组存储二叉树即节省空间，又方便索引（若根结点的序号为 1，那么对于树中任意节点 i，其左子节点序号为 2*i，右子节点序号为 2*i+1）。

为了方便存储和索引，（二叉）堆可以用完全二叉树的形式进行存储。存储的方式如下图所示：

5 堆的操作

堆的更新操作主要包括两种：插入元素和删除堆顶元素。操作过程需要着重掌握和理解。

5.1 插入元素

在堆内进行插入的时候，我们会将插入的元素放到最后

5.1.1 将要插入的元素放到最后

5.1.2 从底向上，如果父结点比该元素小，则该结点和父结点交换 ，直到无法交换

 

5.2 删除堆顶元素（这里拿最大堆举例）

 根据堆的性质可以知道，最大堆的堆顶元素为所有元素中最大的，最小堆的堆顶元素是所有元素中最小的。当我们需要多次查找最大元素或者最小元素的时候，可以利用堆来实现。

删除堆顶元素后，为了保持堆的性质，需要对堆的结构进行调整，我们将这个过程称之为“堆化”，堆化的方法分为两种：

• 一种是自底向上的堆化，上述的插入元素所使用的就是自顶向上的堆化，元素是从最底部向上移动。
• 另一种是自顶向下堆化，元素由最顶部向下移动。

5.2.1 自底向上堆化

打个比方，如果一个公司里出现了boss离职的情况，该怎么办，看下文

首先删除堆顶元素，使得数组中下标为1的位置空出。

那谁来顶替这个位置，必须是数足够大。所以我们比较根结点的左子结点和右子结点，也就是下标为2,3的数组元素，将较大的元素填充到根结点的位置。

这时候，空出来的位置，就依次往下递归，谁有能力谁就上。也就是说，一直循环比较空出位置的左右子结点，并将大者移至空位，直到遍历到堆的最底部。

 

我们可以看到，这个时候已经完成了自底向上的堆化，没有元素可以填补空缺了，但是，我们可以看到数组中出现了空白，这将会导致存储空间的浪费。

5.2.2 自顶向下堆化 

自顶向下堆化，有一个特殊的点就是我们需要将堆的最后一个元素从末尾的位置提到堆顶（根结点）上来，再进行堆化。

 

我们不断的将这个（原来的） 末尾元素，不断地与左右子结点的值进行比较，和较大的子结点交换位置，直到无法交换为止

可能有的小伙伴要问了，这两个也没有什么太大的区别啊，重点就在自顶向下堆化不会产生气泡。

5.3 总结堆的操作

• 插入元素：先将元素放置到元素末尾，再自底向上堆化，使末尾元素上浮。
• 删除堆顶元素：将末尾元素放置堆顶，再自顶向下堆化，将堆顶元素下沉。也可以自底向上堆化，只是会产生空缺，浪费存储空间。最好采用自顶向下的堆化方式。

6 堆排序

堆排序的过程分为两步：

1. 第一步是建堆，将一个无序的数组建立为一个堆。
2. 第二步是排序，将堆顶元素取出，然后对剩下的元素进行堆化，反复迭代，直到所有的元素被取出为止。

6.1 建堆

建堆的过程就是一个对所有非叶子结点的自顶向下堆化过程。

什么是非叶子结点，就是最后一个结点的父结点及它之前的元素，都是非叶子结点（具体可以了解另外一篇关于树的相关内容，这里不详谈）。数据结构秘籍（三）树 （含二叉树的分类、存储和定义）-CSDN博客文章浏览阅读689次，点赞27次，收藏22次。根结点的序号为1，对于每个结点Node，假设它存储在数组中下标为i的位置，那么它的左子结点就存储在2i的位置，它的右子结点就存储在下标为2i+1的位置。二叉树的第i层最多拥有2的（n-1）次方个结点，深度为k的二叉树至多有2^(k+1)-1个结点（满二叉树），至少有2的n次方个结点，这里面的k为深度。二叉树的先序遍历是先输出根结点，再遍历左子树，最后遍历右子树，遍历右子树和左子树的时候同样 遵循先序遍历的规则，也就是说，我们可以递归实现先序遍历。并且，二叉树的分支具有左右次序，不能随意颠倒。https://blog.csdn.net/rc1596919047/article/details/145934474?spm=1001.2014.3001.5501也就是说，如果结点个数为n，那么我们需要对n/2到1的结点进行自顶向下堆化。

将初始的无序数组抽象为一棵树，图中的结点个数为6个，所以4，5，6结点为叶子结点，1,2,3结点为非叶子结点，所以要对1-3号结点进行自顶向下堆化，注意顺序是从后往前堆化，从3号结点开始，一直到1号结点。（为什么是结点3，n为6，非叶子结点就是3-1）。

例如这张图，非叶子结点就是从5开始到1。（画的比较抽象，不喜勿喷）

回去看，3号结点堆化结果：

 2号结点堆化结果：

1号结点堆化结果：

 

至此，数组所对应的树已经成为了一个最大堆，建堆完成。

额外注意的是，堆化是一个完整的过程，而非一个步骤。

6.2 排序

由于堆顶元素是所有元素中最大的，所以我们重复取出堆顶元素，将这个最大的堆顶元素放置数组末尾，并对剩下的元素进行堆化即可。

现在思考两个问题：

1. 删除堆顶元素后需要执行自顶向下堆化，还是自底向上堆化？
2. 取出的堆顶元素存在哪，新建一个数组存吗？

先回答第一个问题，我们需要执行自顶向下堆化，这个堆化一开始要将末尾元素移动至堆顶，这个时候末尾的位置就空出来了，由于堆中的元素已经减小，这个位置不会再被使用，所以我们可以将取出的元素放在末尾。这其实就是做了一次交换操作，将堆顶和末尾的元素调换位置，从而将取出堆顶元素和堆化的第一步（将末尾元素放置根结点）进行合并。

取出第一个元素并堆化：

取出第二个元素并堆化：

取出第三个元素并堆化：

 

取出第四个元素并堆化：

 

取出第五个元素并堆化：

 

取出第六个元素并堆化：

堆排序就此完成。 

如果觉得我的讲解有不足之处，可以在评论区发表意见，我会及时采纳改正。更细致的，可以去看一看这篇文章：

数据结构堆(Heap)详解-堆的建立、插入、删除、最大堆、最小堆、堆排序等_最大堆 heap 是一个什么样的存在?-CSDN博客文章浏览阅读7.9w次，点赞153次，收藏447次。基本概念：1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。什么是堆？堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；..._最大堆 heap 是一个什么样的存在?https://blog.csdn.net/xiaomucgwlmx/article/details/103522410