算法基础：优先队列

算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第四篇《优先队列》，非常赞！希望对大家有帮助，大家会喜欢！

前面系列文章：

• 归并排序
• #算法基础#选择和插入排序
• 由快速排序到分治思想

当外面处理一些数据时，外面不一定要求他是整个都是有序的，很多时候我们值需要其中一部分元素就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，但是平均来看快速排序的速度还是比优先队列跟快，所有速度上还是有缺陷的。

但他有个优点在堆上就可以直接取最大值，这样便于我们拿到最大值。

应用场景：

模拟系统，任务调度，数值计算，最小生成数