关于java:一分钟带你学懂什么是堆

上一篇的「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 实际上是用 数组 来实现的。

这个数组的排列形式有点特地，因为它总会保护你定义的（或者默认的）优先级最高的元素 在数组的首位，所以不是轻易一个数组都叫「堆」，实际上，它在你心里，应该是一棵「齐全二叉树」。

这棵齐全二叉树，只存在你心里和各大书本上；理论在在内存里，哪有什么树？就是数组罢了。

那为什么齐全二叉树能够用数组来实现？是不是所有的树都能用数组来实现？

这个就波及齐全二叉树的性质了，咱们下一篇会细讲，简略来说，因为齐全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是间断存储的，所以能够用数组来寄存；第二个问题当然是否。

堆的特点

1. 堆是一棵齐全二叉树；
2. 堆序性 (heap order): 任意节点都 优于 它的 所有孩子。

   a. 如果是任意节点都 大于 它的所有孩子，这样的堆叫 大顶堆，Max Heap;

   b. 如果是任意节点都 小于 它的所有孩子，这样的堆叫 小顶堆，Min Heap;

左图是小顶堆，能够看出对于每个节点来说，都是小于它的所有孩子的，留神是 所有孩子，包含孙子，曾孙 …

1. 既然堆是用数组来实现的，那么咱们能够找到每个节点和它的父母 / 孩子之间的关系，从而能够间接拜访到它们。

比方对于节点 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…