点击上方"java全栈技术"关注，每天学习一个java知识点
转自：程序员小灰
队列的特点是什么？
聪明的小伙伴们都知道，是先进先出（FIFO）。
入队列：
出队列：
那么，优先队列又是什么样子呢？
优先队列不再遵循先入先出的原则，而是分为两种情况：
最大优先队列，无论入队顺序，当前最大的元素优先出队。
最小优先队列，无论入队顺序，当前最小的元素优先出队。
比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：
要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，最坏时间复杂度O（n），并不是最理想的方式。
至于为什么最坏时间复杂度是O（n），大家可以思考下。
让我们回顾一下二叉堆的特性：
1.最大堆的堆顶是整个堆中的最大元素
2.最小堆的堆顶是整个堆中的最小元素
因此，我们可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。
入队操作：
1.插入新节点5
2.新节点5上浮到合适位置。
出队操作：
1.把原堆顶节点10“出队”
2.最后一个节点1替换到堆顶位置
3.节点1下沉，节点9成为新堆顶
代码中采用数组来存储二叉堆的元素，因此当元素超过数组范围的时候，需要进行resize来扩大数组长度。
分享到:
閱讀更多 java全棧技術 的文章
