程序员必学的数据结构|堆

之前不少好友说要讲一下数据结构。简单的数据像数组、栈、队列就不说了，这个比较简单，接下来我们来讨论一些像树、堆、图等数据结构。当然，还有很多更高级的。有机会再谈一谈吧。

今天我们来学习堆，学习一个数据结构之前，我们还是先来了解一下这个东西在干什么用的吧。相信大家都知道并用过有一个类，优先队列。很多优先队列的内部实现就是堆。此外，堆还可以用来排序，还可以进行一些算法的优化。我们后续有机会再继续介绍。

这不是一篇教程，只是根据我对堆的理解，总结一些性质。我们还是使用问答的形式。

第一，什么是堆？

数据结构中的堆跟平时我们讲的内存的堆还是有点区别的。数据结构中的堆其实是利用完全二叉树的结构来维护一组数据。

好了，怎么又引入一个概念了，什么是完全二叉树。

若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

就像这样：

第二，堆的分类：

一般我们把堆分为大根堆与小根堆，也称最大堆，最小堆。顾名思义，就是堆的每个节点都大于它的子孙节点称为大根堆，堆的每个节点小于他的左右子孙节点称为小根堆。

注意到，在堆中，兄弟之间并没有大小关系，只跟父节点有大小关心。

第三，堆有哪些操作？

是的，传统的堆只能有这3种操作，如果非要再加一个，那就是初始化。

第四，我们怎么实现一个堆？

因为堆是一颗完全二叉树，所以，我们可以用数组来实现一个堆。这里稍微讲一下为什么数组可以。估计很多人看了不懂，大家可以看第一张图，完全二叉树中，如果我们第一个结点以1开始，那么，对于每一个节点，如果它的下标为x，那么左儿子下标为2x，右儿子下标为2x+1。

在c++中，可以用stl库的，make_heap();pop_heap();push_heap();sort_heap()。

平时开发我们更经常使用基于堆开发的优先队列，如：

java的PriorityQueue，c++的priority_queue；在python中，可以设置queue的priority属性。

这里还是推荐大家手工用数组实现一下。

第五，堆怎么插入一个元素？

我们用一个小根堆来举例说明，首先我们把2插入末尾。下标为13。

13/2=6，他的父亲下标为6，我们发现a[13]<>

6/2 = 3, a[6] < a[3]，="">

插入一个新的元素的步骤可以总结为，将这个元素放到末尾，不停地与他的父亲比较。我们成这个操作为shift_up,上浮。

第六，堆怎么弹出最大（小）元素？

我们还是用上面那一个例子举例，初始状态为：

当我们pop出大根堆，这个时候我们将对堆顶跟最后一个元素交换。

紧接着我们自上一下，1开始，我们先比较它是否比两个儿子当中更小的那一个大，如果是，与那个儿子交换。

重复这个操作，

弹出一个元素的过程可以总结为，与最后一个元素交换，不断下沉。我们称之为shift_down

总结：

数据结构中的堆大概就是这样，因为头条上放源码的效果太差，有兴趣的同学可以自行上网看一下源码，也可以根据上述思路自己尝试实现一个。

为什么我们要学习数据结构？虽然在现实的开发中，有很多的数据结构已经有别人封装好的类，但是学习这些基础的数据结构有利于你理解这些类。并且，有时候你可以根据实际情况，更好的选择使用的类，甚至是进行改造。

接下来几天，我们来讨论一下堆的一些面试题。欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法,一起来学习数据结构。

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。