算法基础：优先队列
算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第四篇《优先队列》，非常赞！希望对大家有帮助，大家会喜欢！
前面系列文章：
当外面处理一些数据时，外面不一定要求他是整个都是有序的，很多时候我们值需要其中一部分元素就ok了，列如最大值，最小值。这些值就是你希望他们先出来的数值，所有我们下面要说的排序方法就是优先队列啦。
优先队列是一种基于堆有序的排序方式，所有在介绍优先队列之前我们可以先聊聊堆有序。堆有序 就是堆中所有的节点的根节点都大于它的两个子节点 它就被称为堆有序了，看到这里 我相信你知道我们为什么要说堆有序了。
堆有序实现（核心代码）
下沉（要是根节点比子节点小）
private void sink(int k) {
// TODO Auto-generated method stub
int j=2*k; //根节点位置一般在2k或2k-1
while(j<N&&less(k,j)){ //根节点和2k那个节点对比
if(less(j,j+1))j=j+1; //两个子节点对比
exch(k,j); //换位置
k=j; //换位置
}
}
上浮和他差不多逻辑 就上代码了 就是子节点比根节点大 做交换。
对排序的就是基于上面的下沉代码，把每一个数和根节点做交换并下沉
public void sort(Comparable[] a){
int len=a.length;
for(int i=len/2;i>0;i--){ //改造堆
sink(a,i,len);
}
while(len>1){
exch(a,1,len--); //把每一个放到第一个
sink(a,1,len); //做下沉
}
}
堆有序实现了 优先队列就是在这个有序堆上取最大的一个数delMax（）就可以了 知道对取完 就得到了一个优先对列了
public Key delMax(){
Key t= qp[1];
exch(1,N--);
qp[N+1]=null;
sink(1);
return t;
}
特性：便于取某些特定值例如最大值 最小值（把下沉的值的判断换一下就可以了），时间复杂度：NLogN，空间复杂度： 1，多索引稳定：不稳定。
优缺点：
和归并排序对比 ，归并排序是多索引稳定的，而优先队列不稳定，所有优先队列做不了多索引排序的功能。
和快速排序对比，虽说他们的时间复杂度都是NLogN，但是平均来看快速排序的速度还是比优先队列跟快，所有速度上还是有缺陷的。
但他有个优点在堆上就可以直接取最大值，这样便于我们拿到最大值。
应用场景：
模拟系统，任务调度，数值计算，最小生成数
加入技术讨论群
为了方便大家相互交流学习，社区群人数已经2500+，欢迎大家加下面助手微信，拉大家进群，*交流。
喜欢QQ群的，可以扫描下面二维码：
欢迎大家通过二维码打赏支持技术社区（英雄请留名，社区感谢您，打赏次数超过50+）：