数据结构秘笈（四） 堆 （详细包罗用途、分类、存储、利用等）

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 堆排序

堆排序的过程分为两步：

• 第一步是建堆，将一个无序的数组创建为一个堆。
  
• 第二步是排序，将堆顶元素取出，然后对剩下的元素举行堆化，反复迭代，直到全部的元素被取出为止。
  

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 排序

由于堆顶元素是全部元素中最大的，以是我们重复取出堆顶元素，将这个最大的堆顶元素放置数组末了，并对剩下的元素举行堆化即可。
现在思考两个标题：

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

先回复第一个标题，我们必要实行自顶向下堆化，这个堆化一开始要将末了元素移动至堆顶，这个时间末了的位置就空出来了，由于堆中的元素已经减小，这个位置不会再被利用，以是我们可以将取出的元素放在末了。这着实就是做了一次交换利用，将堆顶和末了的元素变更位置，从而将取出堆顶元素和堆化的第一步（将末了元素放置根结点）举行归并。
取出第一个元素并堆化：

取出第二个元素并堆化：

取出第三个元素并堆化：
 

取出第四个元素并堆化：
 

取出第五个元素并堆化：
 

取出第六个元素并堆化：

堆排序就此完成。 

如果以为我的教学有不敷之处，可以在品评区发表意见，我会实时接纳改正。更过细的，可以去看一看这篇文章：
数据结构堆(Heap)详解-堆的创建、插入、删除、最大堆、最小堆、堆排序等_最大堆 heap 是一个什么样的存在?-CSDN博客文章欣赏阅读7.9w次，点赞153次，收藏447次。根本概念：1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部到达最大值，且第h层的全部结点都会集在左子树。2、满二叉树：满二叉树是一种特别的的完全二叉树，全部层的结点都是最大值。什么是堆？堆（英语：heap)是盘算机科学中一类特别的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满意下列性子：堆中某个节点的值总是不大于或不小于其父节点的值；..._最大堆 heap 是一个什么样的存在?

https://blog.csdn.net/xiaomucgwlmx/article/details/103522410



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告