算法：优先队列-理论
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_43126117/article/details/96994418
优先队列
我们先回忆一下什么是队列，队列，一种先进先出的数据结构。主要关注点在于先入的元素先出。
队列
我们先看一下百度百科关于优先队列的介绍
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。
在普通队列的基础上，在添加元素进队列之前，就已经为元素设置好优先级，这个优先级可以是最大值、最小值、出现次数、达到某个限度的因数等等。
我们平时比较常见的优先队列的场景有什么？
军训排队，最矮的在前面，最高的在后面。
电脑操作系统（window10），交互功能的进程优先级高。
生活工作中，自己感觉重要的事情先做。
这些我们编排好优先级的事情，不管入队的顺序如何，都是优先级高的先出队。
优先队列的实现机制
堆（二叉堆、多项式堆、斐波拉契堆...）
二叉搜索树
优先队列的实现有很多种，常见的就是上面这几种，后面会给出实现的详细介绍。
java的优先队列是怎么实现的？
先看一下Java中优先队列的继承体系和实现方法吧。
优先队列也是继承抽象队列，实现队列接口，那么也就有接口中规定的方法了呗（add、offer、clear、poll、peek...)
我们进一步观察源码发现，Java中优先队列是基于最小堆，是一个完全平衡二叉树。通过传递一个comparator或者collection对象，可以实现自定义优先级。下面，我们通过源码来看看添加方法。
package java.util.PriorityQueue;
public boolean offer(E e) { //添加方法
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) //判断size是否大于数组
grow(i + 1); //数组自动扩容
size = i + 1;
if (i == 0)
queue[0] = e; //根节点
else
siftUp(i, e); //传递数组下标和元素
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x); //传入了比较器的
else //默认比较器
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) { //默认比较器
Comparable<? super E> key = (Comparable<? super E>) x; //拿到当前元素x的比较器
while (k > 0) { //迭代
int parent = (k - 1) >>> 1; //无字符移位运算符，k为正数，相当于>>1 ，也就是除2.
Object e = queue[parent]; //获取父节点元素
if (key.compareTo((E) e) >= 0) //调用当前元素比较器，当前节点大于父节点，则停止迭代，保存当前元素到下标为K的数组
break;
queue[k] = e; //把父节点保存在下标为K的数组中
k = parent; //把刚刚父节点的下标保存在K中
}
queue[k] = key; //迭代结束 ， 保存当前元素到特定下标的数组中
}
//假如存入的元数是整型，这个整型的比较器如下
package java.lang.Integer;
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}这就是Java中内置的优先队列的offer方法，通过调用传入元素的比较器，与父节点比较，再次迭代，进而决定元素存储下标，最后保存到数组中。
如果调用的是poll方法，那么运行过程思路如下：先获取下标为0的数组元素和再次堆化（即，再次的运用比较器，生成有根节点的树）。这个小顶堆只是确保最小值在数组[0]位上，其他元素的大小位置是不一定的，只有每次入队出队，再通过比较器，把最小值移动到数组[0]上。
腾讯云开发者
