一、概念定义
我们已经知道
队列是一种先进先出（FIFO）的数据结构
，但是有些情况下，队列不能满足我们的一些需求，
我们需要根据元素的优先级来进行操作，优先级高的元素先出队列。
例如：
-
医院的夜间门诊系统
队列元素是病人对象
优先级是病人的病情严重情况、挂号时间
-
电商网站的特卖、抢购系统
当用户提交订单请求时，可以将普通用户和VIP用户的订单都放入队列里，普通用户的优先级别最低，VIP用户根据其会员等级来决定优先级，即使普通用户和VIP用户同时下单，级别高的用户可以先抢购到商品。如果在全都是普通用户的情况下，则根据用户的下单时间来出队。
在上面这些场景下，后台操作的数据具有优先级，那么普通的队列就在这里不适合，所以我们需要用到
优先级队列PriorityQue
。
优先级队列应该提供两个最基本的操作：
一是返回最高优先级对象；二是添加新的对象
。
二、优先级队列的结构
2.1 堆的概念定义
JDK1.8中的
PriorityQueue底层使用了堆的数据结构
，那么我们先了解一下堆的概念。
堆通常是一个可以被看做一棵二叉树的数组对象。堆总是满足下列性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值；
- 堆总是一颗完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1, k2, k3, …, kn}当且仅当满足下关系时，称之为堆。
若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1, k2, k3, …, kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
2.2 堆的存储方式
从堆的概念知道，
堆是一棵完全二叉树，以层序的规则采用顺序的方式来高效存储。
大根堆示意图
：
如果是非完全二叉树，则不适合使用顺序方式来存储
，因为为了能够还原二叉树，数组空间里必须要存储空结点，就会导致空间利用率比较低。
如下图的非完全二叉树：
将元素存储到数组中后，可以根据二叉树的性质5对树进行还原。假设i为节点在数组中的下标，则有：
- 如果i为0，则i表示的节点为根结点，否则i结点的双亲结点为(i-1)/2。
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子。
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
2.3 堆的创建
2.3.1 堆向下调整
给定一个序列{ 27,15,19,18,28,34,65,49,25,37 }，如何将构建成堆？
首先我们将其展现为完全二叉树的形式：
仔细观察上图可以发现，
除根节点外，其左右子树已经满足堆的性质，即为小根堆
，所以我们通过从根节点开始向下调整，可以将它构建成堆。
向下调整算法过程：
通过一对指针（父节点指针，下文用
parent
代指 和 孩子节点指针，下文用
child
代指）来进行调整。
- 首先将parent指向下标0的位置，通过parent来求child的位置 (parent-1)/2 （注意：如果父节点有孩子，则一定是先有左孩子），再判断是否有右孩子，然后根据左孩子节点+1得出右孩子节点）。
- 比较出左右孩子节点的较小值并使child指向它，再将parent与child比较，如果parent大于child的话就进行交换。
- 交换之后parent大的节点值向下移动可能导致子树不满足堆的性质，需要修改parent和child的指向来继续向下调整，将parent = child, child = parent * 2 + 1 然后重复2操作。
- 如果parent的左孩子不存在了，则parent为叶子节点了，调整结束。
调整图解过程：
实现代码：
private void shiftDown(int parent,int len){
int child = parent * 2 + 1; //左孩子结点
while(child < len){ //如果孩子结点索引等于或大于len,则不存在该孩子结点，其双亲结点为叶子结点
//比较左右孩子结点值的大小
if(child + 1 < len && elem[child] < elem[child+1]){ //(child+1 < len)判断是否有右孩子
child++; //child结点一定记录值大的那个
}
//这里创建大根堆，比较孩子结点是否大于双亲结点
if(elem[child] > elem[parent]){ //大于就交换
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
//因为被调整的孩子结点可能也是其他孩子的双亲结点，所以继续向下调整
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
2.3.2 堆的创建
如果想把序列{ 27,15,19,18,28,34,65,49,25,37 } 调整为大根堆，此时根节点的左右子树不满足堆的性质，我们不能在这里通过向下调整来完成，相反，我们要使用
向上调整
。
调整图解过程：
实现代码：
//调整堆（将初始堆调整为大根堆或小根堆）
public void createHeep(){
//从最后一个结点的双亲结点开始调整
int len = elem.length;
for(int i = (len - 1 - 1) / 2; i >= 0; i--){
shiftDown(i,len);
}
}
private void shiftDown(int parent,int len){
int child = parent * 2 + 1; //左孩子结点
while(child < len){ //如果孩子结点索引等于或大于len,则不存在该孩子结点，其双亲结点为叶子结点
//比较左右孩子结点值的大小
if(child + 1 < len && elem[child] < elem[child+1]){ //(child+1 < len)判断是否有右孩子
child++; //child结点一定记录值大的那个
}
//这里创建大根堆，比较孩子结点是否大于双亲结点
if(elem[child] > elem[parent]){ //大于就交换
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
//因为被调整的孩子结点可能也是其他孩子的双亲结点，所以继续向下调整
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
2.3.3 构建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 (时间复杂度本来看的就是 近似值，多几个节点不影响最终结果)
第1层，2^0个节点，需要向下移动h-1层。
第2层，2^1个节点，需要向下移动h-2层。
第3层，2^2个节点，需要向下移动h-3层。
第4层，2^3个节点，需要向下移动h-4层。
…
第h-1层，2^h-2个节点，需要向下移动1层。
推导公式这里直接给出课件里的哈哈！
因此：建堆的时间复杂度为O(N)。
2.4 堆的插入与删除
2.4.1 堆底插入元素
在堆中插入新元素主要分为两个操作：
- 检查数组容量是否足够，不够则扩容，将新元素插入到数组末尾位置，堆元素个数+1。
- 从插入结点开始向上调整，直到满足堆的结构性质。
向上调整算法过程（以大根堆为例）：
- 同向下调整一样使用双指针parent和child,先使child指向新插入结点位置，然后将parent指向 (child-1)/2 父结点位置。
- 比较parent和child的值，如果parent小则交换值，否则直接结束（因为当parent值不小于child值时，已经满足了堆结构性质）。
- 交换之后大的值向上移动可能破坏上层堆的结构，所以需要让child指向parent，parent再重新指向 (child-1)/2 父结点位置，然后重复步骤2。
- 如果child指向了0下标的位置，则调整结束。
插入元素图解过程：
2.4.2 堆顶删除元素
首先要知道我们这里操作的是优先级队列，而队列必须满足
尾进头出
原则，堆顶元素只可能是堆中优先级最高的，先访问的一定是堆顶的元素。
删除堆顶元素也是需要两个操作
-
将堆顶元素与堆尾元素进行交换
，堆元素个数-1。 - 从堆顶结点开始向下调整结构。
向下调整算法过程（以大根堆为例）：
这里的调整算法与上文
堆的创建
中
堆向下调整
逻辑一致，只是比较规则不同（这里是大根堆，所以当parent值小于child值时进行交换），调整的图解过程也一致，所以不再赘述。
三、模拟实现优先级队列容器类
/**
* 模拟实现PriorityQueue优先级队列容器类
* @param <E>
*/
public class MyPriorityQueue2<E extends Comparable<E>> {
//存放堆元素
private Object[] elemData;
//默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//堆元素个数
private int size;
//对象比较器
Comparator<E> comparator;
/**
* 创建默认容量大小的队列对象，并使用元素的自然排序规则
*/
public MyPriorityQueue2(){
this(DEFAULT_INITIAL_CAPACITY,null);
}
/**
* 创建指定容量大小的队列对象，并使用元素的自然排序规则
* @param initialCapacity 指定初始容量
*/
public MyPriorityQueue2(int initialCapacity){
this(initialCapacity,null);
}
/**
* 创建默认初始容量大小的队列对象，并使用指定比较器对象
* @param comparator 指定比较器
*/
public MyPriorityQueue2(Comparator<E> comparator){
this(DEFAULT_INITIAL_CAPACITY,comparator);
}
/**
* 创建指定初始容量大小的队列对象并初始化比较器对象成员
* @param initialCapacity 指定初始容量
* @param comparator 比较器对象
*/
public MyPriorityQueue2(int initialCapacity, Comparator<E> comparator){
this.elemData = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 将指定元素入队列，然后根据比较规则来调整堆结构
* @param e 指定元素对象
* @return true
*/
public boolean offer(E e){
isFull();
int i = size++;
elemData[i] = e;
if(i == 0){ //首次入队
return true;
}
if(comparator == null){
shiftUpWithNaturalSorting(i,size);
}else{
shiftUpWithComparatorSorting(i,size);
}
return true;
}
//使用自然排序比较规则来向上调整
@SuppressWarnings("unchecked")
private void shiftUpWithNaturalSorting(int child,int len){
int parent = (child - 1) / 2;
while (child > 0){
Comparable<E> parentElem = (Comparable<E>) elemData[parent];
if(parentElem.compareTo((E)elemData[child]) > 0){
E temp = (E)elemData[parent];
elemData[parent] = elemData[child];
elemData[child] = temp;
child = parent;
parent = (child - 1) / 2;
}else{
break;
}
}
}
//使用定制排序比较规则来向上调整
@SuppressWarnings("unchecked")
private void shiftUpWithComparatorSorting(int child,int len){
int parent = (child - 1) / 2;
while (child > 0){
if(comparator.compare((E)elemData[parent],(E)elemData[child]) > 0){
E temp = (E)elemData[parent];
elemData[parent] = elemData[child];
elemData[child] = temp;
child = parent;
parent = (child - 1) / 2;
}else{
break;
}
}
}
/**
* 将队列中优先级最高的元素出队
* @return
*/
public E poll(){
if(isEmpty()){
return null;
}
E polled = (E)elemData[0];
elemData[0] = elemData[--size];
if(comparator == null){
shiftDownComparable();
}else{
shiftDownComparator();
}
return polled;
}
@SuppressWarnings("unchecked")
private void shiftDownComparable(){
int parent = 0;
Comparable<E> parentEle = (Comparable<E>) elemData[parent];
int child = 1;
while (child < size){
if(child + 1 < size && ((Comparable<E>)elemData[child]).compareTo((E)(elemData[child+1])) > 0){
child++;
}
if(parentEle.compareTo((E)elemData[child]) > 0){
Object temp = elemData[parent];
elemData[parent] = elemData[child];
elemData[child] = temp;
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
@SuppressWarnings("unchecked")
private void shiftDownComparator(){
int parent = 0;
int child = 1;
while (child < size){
if(comparator.compare((E)elemData[child],(E)elemData[child+1]) > 0){
child++;
}
if(comparator.compare((E)elemData[parent],(E)elemData[child]) > 0){
Object temp = elemData[parent];
elemData[parent] = elemData[child];
elemData[child] = temp;
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
//检查队列空间是否足够，不够就扩容
private void isFull(){
int len = elemData.length;
if(size == len){
elemData = Arrays.copyOf(elemData, len * 2);
}
}
/**
* @return 返回当前堆顶元素，如果堆为空则返回null
*/
@SuppressWarnings("unchecked")
public E peek(){
if (isEmpty()){
return null;
}else{
return (E)elemData[0];
}
}
/**
* @return 队列是否为空
*/
public boolean isEmpty(){
return size == 0;
}
/**
* @return 返回队列元素个数
*/
public int size(){
return size;
}
}
四、Java集合框架中的PriorityQueue
通过类继承图看到PriorityQueue是实现了Queue接口的，所以也实现了队列的基本方法。
在类结构当中有几种重载的构造方法，可以根据不同的形参列表来实例化不同属性的对象。
类当中还有许多基本的方法，这里我们主要关注以下三个。
1. offer(E)
2.poll()
3.peek()
五、优先级队列的应用
示意性的模拟一个优先级队列使用场景，这里拿上文中的
电商网站的特卖、抢购系统
来作例子。
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueTest {
//优先级队列的应用
public static void main(String[] args) {
//准备一批用户对象
User u1 = new User(1001, "张三", MembershipLevel.V8);
User u2 = new User(1002, "李四", MembershipLevel.V5);
User u3 = new User(1003, "王五", MembershipLevel.V5);
User u4 = new User(1004, "赵六", MembershipLevel.V3);
User u5 = new User(1005, "孙七", MembershipLevel.V1);
User u6 = new User(1006, "周八", MembershipLevel.V0);
//假设某商品抢购场景，让所有用户都入队列，然后根据用户会员等级出队，先出队的就可以先抢到
PriorityQueue<User> userPriorityQueue = new PriorityQueue<>(new LevelComparator());
userPriorityQueue.offer(u6);
userPriorityQueue.offer(u5);
userPriorityQueue.offer(u4);
userPriorityQueue.offer(u3);
userPriorityQueue.offer(u2);
userPriorityQueue.offer(u1);
int userNumber = userPriorityQueue.size();
for(int i = 0; i < userNumber; i++){
User user = userPriorityQueue.poll();
if (user != null) {
System.out.println(user.getName() + "是第" + (i+1) + "个抢到商品的。");
}
}
}
}
//用户会员等级
enum MembershipLevel{
V0,V1,V2,V3,V4,V5,V6,V7,V8;
}
//用户类
class User{
private int id;
private String name;
private MembershipLevel level;
public User(int id, String name, MembershipLevel level) {
this.id = id;
this.name = name;
this.level = level;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public MembershipLevel getLevel() {
return level;
}
public void setLevel(MembershipLevel level) {
this.level = level;
}
}
//根据用户会员等级来比较
class LevelComparator implements Comparator<User> {
@Override
public int compare(User o1, User o2) {
return o2.getLevel().compareTo(o1.getLevel());
}
}
这个例子还是比较现实的哈哈。
六、经典面试题Top-K问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
具体的题目讲解就不放在本文讲解了，之后更新到面试题栏目中。