算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第四篇《优先队列》,非常赞!希望对大家有帮助,大家会喜欢!
前面系列文章:
当外面处理一些数据时,外面不一定要求他是整个都是有序的,很多时候我们值需要其中一部分元素就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,但是平均来看快速排序的速度还是比优先队列跟快,所有速度上还是有缺陷的。
但他有个优点在堆上就可以直接取最大值,这样便于我们拿到最大值。
应用场景:
模拟系统,任务调度,数值计算,最小生成数