数据结构面试的常客，一文带你深入了解堆

和链表、二叉树以及数组这些热门的数据结构相比，堆相对比较冷门。如果你对数据结构了解不深的话，可能很少听说。但是我们经常用到它，虽然可能你并不一定能感知到。比如说优先队列，我们就经常使用。我们需要用到这样一个数据结构，能够根据我们存入数据的优先级进行排序，将优先级高的排在前面。在和调度相关的一些系统和算法当中，优先队列是必然会用到的。但是很少有人知道，优先队列说是一个队列，但其实是通过堆实现的。

那么堆究竟是一个怎样的数据结构呢？

堆的定义

堆的实质其实是二叉树，并且还不是一般的二叉树，而是比较特别的二叉树。

特别在什么地方呢，在于这棵二叉树除了叶子之外的所有节点都是“满”的。所谓的满，也就是没有空缺的意思。

从上图当中我们可以看到，如果去掉最后一层，那么这棵二叉树就是全满的。最后一层叶子节点也是有要求的，要求叶子节点都靠左对齐。满足这两个条件的二叉树成为完全二叉树（complete binary tree）。这个概念如果记不住也没有关系，我好像也只在堆当中遇到。

堆是完全二叉树，但是显然不是所有的完全二叉树都是堆，堆还有一个特殊的性质，就是大小的传递性。

堆根据大小传递性的不同分为大顶堆和小顶堆&

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/107034368