如何减少不必要的计算？

比如对于节点 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 开始的，都是可以的。

这样就可以从任意一个点，一步找到它的孙子、曾孙子，真的太方便了，在后文讲具体操作时大家可以更深刻的体会到。

基本操作

任何一个数据结构，无非就是增删改查四大类：


 

也就是说，

• PriorityQueue 是一个类 (class);
• PriorityQueue 继承自 Queue 这个接口 (Interface);

那 heap 在哪呢?

heap 其实是一个抽象的数据结构，或者说是逻辑上的数据结构，并不是一个物理上真实存在的数据结构。

heap 其实有很多种实现方式，比如 binomial heap, Fibonacci heap 等等。但是面试最常考的，也是最经典的，就是 binary heap 二叉堆，也就是用一棵完全二叉树来实现的。

那完全二叉树是怎么实现的?

其实是用数组来实现的!

所以 binary heap/PriorityQueue 实际上是用数组来实现的。

这个数组的排列方式有点特别，因为它总会维护你定义的(或者默认的)优先级最高的元素在数组的首位，所以不是随便一个数组都叫「堆」，实际上，它在你心里，应该是一棵「完全二叉树」。

这棵完全二叉树，只存在你心里和各大书本上;实际在在内存里，哪有什么树?就是数组罢了。

那为什么完全二叉树可以用数组来实现?是不是所有的树都能用数组来实现?

这个就涉及完全二叉树的性质了，我们下一篇会细讲，简单来说，因为完全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是连续存储的，所以可以用数组来存放;第二个问题当然是否。

堆的特点

1.堆是一棵完全二叉树;

2.堆序性 (heap order): 任意节点都优于它的所有孩子。

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

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

（编辑：保山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!