算法基础:优先队列

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

前面系列文章:

当外面处理一些数据时,外面不一定要求他是整个都是有序的,很多时候我们值需要其中一部分元素就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 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】聊聊C语言-第一只螃蟹

上一篇我们介绍了开发C语言需要了解的基础术语和开发C语言常用的工具做好了进行C语言编程的准备,现在我们开始操刀烹炸C语言编程世界的第一道菜-hello wor...

32713
来自专栏程序员互动联盟

【编程之美】最优排序算法

寻找最大的K个数 从n个数中寻找最大的K个数。 01 class 两种思路: 1 保存目前找到的最大k个数,每访问一个数,就与这k个数中的最小值比较,决定是否更...

3387
来自专栏Crossin的编程教室

【Python 第57课】 正则表达式(3)

先来公布上一课习题的答案: \bs\S*?e\b 有的同学给出的答案是"\bs.*?e\b"。测试一下就会发现,有奇怪的'sea sue'和'sweet see...

2406
来自专栏Java 源码分析

Java 虚拟机运行时数据区

运行时数据区: Java 虚拟机的运行时数据区按照大的可以分为线程独立使用的数据区,和所有线程共享的数据区。 一.线程独立使用数据区 1.程序计数器 程序计数器...

2435
来自专栏Golang语言社区

Golang语言--细节汇总

slice和数组在声明时的区别:声明数组时,方括号内写明了数组的长度或使用...自动 计算长度,而声明slice时,方括号内没有任何字符。 对于slice有几个...

3529
来自专栏怀英的自我修炼

Java漫谈6

今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

3409
来自专栏Java 源码分析

Java 虚拟机运行时数据区

运行时数据区: Java 虚拟机的运行时数据区按照大的可以分为线程独立使用的数据区,和所有线程共享的数据区。 一.线程独立使用数据区 1.程序计数器 程序计数器...

3124
来自专栏诸葛青云的专栏

C语言初学者必须掌握的关键字!

其实小伙伴在写代码的时候,关键字还是用的比较多的,老九主要就平常中用到的常用关键字进行总结,便于小伙伴们更全面的理解其在代码中的意图。

30
来自专栏cs

递归算法

据说凡是可以循环的步骤,都可以递归表示出来。 递归的关键有二点: 1.0 递归公式,即递推式。 2.0 递归出口。 ---- 递归求数组的和 package...

3375
来自专栏玄魂工作室

如何学Python 第七课 列表型变量 列表方法 列表索引

在上一篇文章里,我们介绍了if语句、elif语句和else语句以及条件判断语句。我们今天来说点流程控制之外的东西:列表。列表型变量可以在变量下存储多个值,并以索...

3197

扫描关注云+社区