算法基础:优先队列

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

前面系列文章:

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

相关文章

来自专栏MasiMaro 的技术博文

C/C++中整数与浮点数在内存中的表示方式

在C/C++中数字类型主要有整数与浮点数两种类型,在32位机器中整型占4字节,浮点数分为float,double两种类型,其中float占4字节,而double...

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

聊聊C语言-编程世界的容器

上一篇聊聊C语言-存储世界的奥秘,我们介绍了计算机的整个存储体系设计,了解了我们的数据在计算机中是怎么被存储的。然而在我们的编程中我们的代码也是按照这个结构被计...

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

【编程基础】Java 如何完成数据类型转换

在写程序的时候经常遇到数据的运算,在数据运算中又经常遇到不同类型的数据之间进行转换,那么数据类型之间的转换规则是什么样的呢? Java数据类型转换分为两种: ...

2754
来自专栏小狼的世界

Python3.6学习笔记(三)

面向对象编程 Object Oriented Programming 简称 OOP,是一种程序设计思想。OOP把对象作为程序的基本单元,一个对象包含了数据和操作...

752
来自专栏有趣的Python

3-Linux C语言结构体-学习笔记

将#include <stdio.h>中stdio.h展开,将未注释的内容直接写入.i文件。

1841
来自专栏机器学习算法与Python学习

python基础语法(1)

从今天起,将进行python的一个系列学习,从基本的语法学起,后期会推出一些关于web开发,网络爬虫以及用python的第三方库进行数据挖掘与机器学习等高级的开...

37414
来自专栏GreenLeaves

JavaScript引用类型之Array数组的栈方法与队列方法

一、栈方法 ECMAScript数组也提供了一种让数组的行为类似与其他数据结构的方法。具体的来说,数组可以变现的向栈一样,栈就是一种可以限制插入和删除向的数据结...

1846
来自专栏C/C++基础

C++接口继承与实现继承的区别和选择

《Effective C++》条款三十四:区分接口继承和实现继承中介绍的比较啰嗦,概括地说需要理解三点: (1)纯虚函数只提供接口继承,但可以被实现; ...

721
来自专栏我和PYTHON有个约会

22. 企业级开发基础3:类和对象

本节内容开始,讲解企业级项目开发基础部分:面向对象;主要从对象的抽象、对象的创建,对象中特殊的方法,面向对象的封装、继承、多态等各个方面来进行讲解。

643
来自专栏沈唁志

PHP中多维数组自定义排序uasort()

1483

扫码关注云+社区