什么是堆，堆在整个Java集合框架中的作用
堆其实就是一种特殊的队列——优先队列。
普通的队列游戏规则很简单：就是先进先出；但这种优先队列搞特殊，不是按照进队列的时间顺序，而是按照每个元素的优先级来比拼，优先级高的在堆顶。
这也很容易理解吧，比如各种软件都有会员制度，某软件用了会员就能加速下载的，不同等级的会员速度还不一样，那就是优先级不同呀。
还有其实每个人回复微信消息也是默默的把消息放进堆里排个序：先回男朋友女朋友的，然后再回其他人的。
这里要区别于操作系统里的那个“堆”，这两个虽然都叫堆，但是没有半毛钱关系，都是借用了heap这个英文单词而已。
我们再来回顾一下「堆」在整个java集合框架中的位置：
也就是说，
priorityqueue是一个类(class)；
priorityqueue继承自queue这个接口(interface)；
那heap在哪呢？
heap其实是一个抽象的数据结构，或者说是逻辑上的数据结构，并不是一个物理上真实存在的数据结构。
heap其实有很多种实现方式，比如binomialheap,fibonacciheap等等。但是面试最常考的，也是最经典的，就是binaryheap二叉堆，也就是用一棵完全二叉树来实现的。
那完全二叉树是怎么实现的？
其实是用数组来实现的！
所以binaryheap/priorityqueue实际上是用数组来实现的。
这个数组的排列方式有点特别，因为它总会维护你定义的（或者默认的）优先级最高的元素在数组的首位，所以不是随便一个数组都叫「堆」，实际上，它在你心里，应该是一棵「完全二叉树」。
这棵完全二叉树，只存在你心里和各大书本上；实际在在内存里，哪有什么树？就是数组罢了。
那为什么完全二叉树可以用数组来实现？是不是所有的树都能用数组来实现？
这个就涉及完全二叉树的性质了，我们下一篇会细讲，简单来说，因为完全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是连续存储的，所以可以用数组来存放；第二个问题当然是否。
堆的特点
堆是一棵完全二叉树；
堆序性(heaporder):任意节点都优于它的所有孩子。
a.如果是任意节点都大于它的所有孩子，这样的堆叫大顶堆，maxheap;
b.如果是任意节点都小于它的所有孩子，这样的堆叫小顶堆，minheap;
左图是小顶堆，可以看出对于每个节点来说，都是小于它的所有孩子的，注意是**所有孩子，包括孙子，曾孙...**
既然堆是用数组来实现的，那么我们可以找到每个节点和它的父母/孩子之间的关系，从而可以直接访问到它们。
比如对于节点3来说，
它的index=1，
它的parentindex=0,
左孩子leftchildindex=3,
右孩子rightchildindex=4.
可以归纳出如下规律：
设当前节点的index=x,
那么parentindex=(x-1)/2,
左孩子leftchildindex=2*x+1,
右孩子rightchildindex=2*x+2.
有些书上可能写法稍有不同，是因为它们的数组是从1开始的，而我这里数组的下标是从0开始的，都是可以的。
这样就可以从任意一个点，一步找到它的孙子、曾孙子，真的太方便了，在之后讲具体操作时大家可以更深刻的体会到。
那有关堆的基本操作，以及为什么heapify()是o(n)的，我们之后再聊。
真“水下无人机”：世界第一架能飞能潜水的无人机？
电动势和电压的方向
电容器三段式过流原理是什么？
华为荣耀V9幻夜黑版明日首发：快到极致黑得漂亮，惊艳你的不止是速度！
英特尔八代酷睿盒装处理器全面涨价
什么是堆，堆在整个Java集合框架中的作用
用于各类摄像应用的高速CMOS图像传感器
大众ID.4供电控制技术浅析
全方面评测东风启辰D60 1.6L CVT
根据电机额定转速计算电机额定转速时电子齿轮比、脉冲当量
美国国家半导体推出无线基站中频采样接收器子系统
燃油车电子电气架构改变 从传统的分布式ECU到域控制器
串口和并口的区别是什么
双11黑马出现，iQOO品牌销售额杀入安卓阵营TOP2
虹识技术家庭用联网式锁解决方案
对答如流不见“人”智能外呼机器人全面升级
锡膏保存及使用注意事项
基于STM32、FreeRTOS 实现硬件看门狗+软件看门狗监测多任务的方法
现代化羽毛球场馆智能照明控制系统羽毛球场馆灯光设计
华为nova2什么时候上市？华为nova2最新消息：华为Nova2要用麒麟659？跑分与骁龙626相当
普通的队列游戏规则很简单：就是先进先出；但这种优先队列搞特殊，不是按照进队列的时间顺序，而是按照每个元素的优先级来比拼，优先级高的在堆顶。
这也很容易理解吧，比如各种软件都有会员制度，某软件用了会员就能加速下载的，不同等级的会员速度还不一样，那就是优先级不同呀。
还有其实每个人回复微信消息也是默默的把消息放进堆里排个序：先回男朋友女朋友的，然后再回其他人的。
这里要区别于操作系统里的那个“堆”，这两个虽然都叫堆，但是没有半毛钱关系，都是借用了heap这个英文单词而已。
我们再来回顾一下「堆」在整个java集合框架中的位置：
也就是说，
priorityqueue是一个类(class)；
priorityqueue继承自queue这个接口(interface)；
那heap在哪呢？
heap其实是一个抽象的数据结构，或者说是逻辑上的数据结构，并不是一个物理上真实存在的数据结构。
heap其实有很多种实现方式，比如binomialheap,fibonacciheap等等。但是面试最常考的，也是最经典的，就是binaryheap二叉堆，也就是用一棵完全二叉树来实现的。
那完全二叉树是怎么实现的？
其实是用数组来实现的！
所以binaryheap/priorityqueue实际上是用数组来实现的。
这个数组的排列方式有点特别，因为它总会维护你定义的（或者默认的）优先级最高的元素在数组的首位，所以不是随便一个数组都叫「堆」，实际上，它在你心里，应该是一棵「完全二叉树」。
这棵完全二叉树，只存在你心里和各大书本上；实际在在内存里，哪有什么树？就是数组罢了。
那为什么完全二叉树可以用数组来实现？是不是所有的树都能用数组来实现？
这个就涉及完全二叉树的性质了，我们下一篇会细讲，简单来说，因为完全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是连续存储的，所以可以用数组来存放；第二个问题当然是否。
堆的特点
堆是一棵完全二叉树；
堆序性(heaporder):任意节点都优于它的所有孩子。
a.如果是任意节点都大于它的所有孩子，这样的堆叫大顶堆，maxheap;
b.如果是任意节点都小于它的所有孩子，这样的堆叫小顶堆，minheap;
左图是小顶堆，可以看出对于每个节点来说，都是小于它的所有孩子的，注意是**所有孩子，包括孙子，曾孙...**
既然堆是用数组来实现的，那么我们可以找到每个节点和它的父母/孩子之间的关系，从而可以直接访问到它们。
比如对于节点3来说，
它的index=1，
它的parentindex=0,
左孩子leftchildindex=3,
右孩子rightchildindex=4.
可以归纳出如下规律：
设当前节点的index=x,
那么parentindex=(x-1)/2,
左孩子leftchildindex=2*x+1,
右孩子rightchildindex=2*x+2.
有些书上可能写法稍有不同，是因为它们的数组是从1开始的，而我这里数组的下标是从0开始的，都是可以的。
这样就可以从任意一个点，一步找到它的孙子、曾孙子，真的太方便了，在之后讲具体操作时大家可以更深刻的体会到。
那有关堆的基本操作，以及为什么heapify()是o(n)的，我们之后再聊。
真“水下无人机”：世界第一架能飞能潜水的无人机？
电动势和电压的方向
电容器三段式过流原理是什么？
华为荣耀V9幻夜黑版明日首发：快到极致黑得漂亮，惊艳你的不止是速度！
英特尔八代酷睿盒装处理器全面涨价
什么是堆，堆在整个Java集合框架中的作用
用于各类摄像应用的高速CMOS图像传感器
大众ID.4供电控制技术浅析
全方面评测东风启辰D60 1.6L CVT
根据电机额定转速计算电机额定转速时电子齿轮比、脉冲当量
美国国家半导体推出无线基站中频采样接收器子系统
燃油车电子电气架构改变 从传统的分布式ECU到域控制器
串口和并口的区别是什么
双11黑马出现，iQOO品牌销售额杀入安卓阵营TOP2
虹识技术家庭用联网式锁解决方案
对答如流不见“人”智能外呼机器人全面升级
锡膏保存及使用注意事项
基于STM32、FreeRTOS 实现硬件看门狗+软件看门狗监测多任务的方法
现代化羽毛球场馆智能照明控制系统羽毛球场馆灯光设计
华为nova2什么时候上市？华为nova2最新消息：华为Nova2要用麒麟659？跑分与骁龙626相当