算法基础:优先队列

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

前面系列文章:

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

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

应用场景:

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

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-01-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1282
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

771
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7475
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏码匠的流水账

聊聊spring cloud的HystrixAutoConfiguration

本文主要研究一下spring cloud的HystrixAutoConfiguration

972

扫码关注云+社区