上一篇的「Java 汇合框架」里，还剩下一个大问题没有说的，那就是 PriorityQueue，优先队列，也就是堆，Heap。
什么是堆？
堆其实就是一种非凡的队列——优先队列。
一般的队列游戏规则很简略：就是先进先出；但这种优先队列 搞非凡 ，不是依照进队列的工夫程序，而是依照每个元素的 优先级 来比拼，优先级高的在堆顶。
这也很容易了解吧，比方各种软件都有会员制度，某软件用了会员就能减速下载的，不同等级的会员速度还不一样，那就是优先级不同呀。
还有其实每个人回复微信音讯也是默默的把音讯放进堆里排个序：先回男朋友女朋友的，而后再回其他人的。
这里要区别于操作系统里的那个“堆”，这两个尽管都叫堆，然而没有半毛钱关系，都是借用了 Heap 这个英文单词而已。
咱们再来回顾一下「堆」在整个 Java 汇合框架中的地位：
也就是说，
- PriorityQueue 是一个类 (class)；
- PriorityQueue 继承自 Queue 这个接口 (Interface)；
<span style=”display:block;color:blue;”> 那 heap 在哪呢？
heap 其实是一个 形象的数据结构 ，或者说是 逻辑上的数据结构，并不是一个物理上实在存在的数据结构。
<span style=”;color:blue;”>heap 其实有很多种实现形式，</span> 比方 binomial heap, Fibonacci heap 等等。然而面试最常考的，也是最经典的，就是 binary heap 二叉堆 ，也就是用一棵 齐全二叉树 来实现的。
<span style=”display:block;color:blue;”> 那齐全二叉树是怎么实现的？
其实是用 数组 来实现的！
所以 binary heap/PriorityQueue 实际上是用 数组 来实现的。
这个数组的排列形式有点特地，因为它总会保护你定义的（或者默认的）优先级最高的元素 在数组的首位，所以不是轻易一个数组都叫「堆」，实际上，它在你心里，应该是一棵「齐全二叉树」。
这棵齐全二叉树，只存在你心里和各大书本上；理论在在内存里，哪有什么树？就是数组罢了。
那为什么齐全二叉树能够用数组来实现？是不是所有的树都能用数组来实现？
这个就波及齐全二叉树的性质了，咱们下一篇会细讲，简略来说，因为齐全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是间断存储的，所以能够用数组来寄存；第二个问题当然是否。
堆的特点
- 堆是一棵齐全二叉树；
- 堆序性 (heap order): 任意节点都 优于 它的 所有孩子。
a. 如果是任意节点都 大于 它的所有孩子，这样的堆叫 大顶堆，Max Heap;
b. 如果是任意节点都 小于 它的所有孩子，这样的堆叫 小顶堆，Min Heap;
左图是小顶堆，能够看出对于每个节点来说，都是小于它的所有孩子的，留神是 所有孩子，包含孙子，曾孙 …
- 既然堆是用数组来实现的，那么咱们能够找到每个节点和它的父母 / 孩子之间的关系，从而能够间接拜访到它们。
比方对于节点 3 来说，
- 它的 Index = 1，
- 它的 parent index = 0,
- 左孩子 left child index = 3,
- 右孩子 right child index = 4.
能够演绎出如下法则：
- 设以后节点的 index = x,
- 那么 parent index = (x-1)/2,
- 左孩子 left child index = 2*x + 1,
- 右孩子 right child index = 2*x + 2.
有些书上可能写法稍有不同，是因为它们的数组是从 1 开始的，而我这里数组的下标是从 0 开始的，都是能够的。
这样就能够从任意一个点，一步找到它的孙子、曾孙子，真的太不便了，在之后讲具体操作时大家能够更粗浅的领会到。
那无关堆的基本操作，以及为什么 heapify() 是 O(n) 的，咱们之后再聊。
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…