算法基础:优先队列

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

前面系列文章:

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

相关文章

来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

4514
来自专栏wym

线段树理论基础

线段树(segment tree)是一种二叉搜索树,它的每一个结点对应着一个区间[L,R],叶子节点对应的是一个单位区间,即L==R。

963
来自专栏温安适的blog

读书笔记-红黑树

2677
来自专栏机器学习入门

LWC 52:688. Knight Probability in Chessboard

LWC 52:688. Knight Probability in Chessboard 传送门:688. Knight Probability in Ches...

2058
来自专栏小鹏的专栏

堆排序

堆排序排序是优秀的算法,但是在实际应用中,快速排序的性能一般会优于堆排序, 尽管如此,堆排序仍然有很多应用,例如:作为高效的优先队列,最大优先队列应用于共享计算...

1896
来自专栏数据结构与算法

洛谷P2345 奶牛集会

题目背景 MooFest, 2004 Open 题目描述 约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很 多,比如堆干草,跨栅...

3024
来自专栏用户画像

7.7.3 多路平衡归并与败者树

归并趟数S=[logm R](向下取整)。从而增加归并路数m可以减少归并趟数S,进而减少访问外存的次数(I/O次数)。然而,当增加归并路数m时,内部归并时间将增...

542
来自专栏IT可乐

Java数据结构和算法(十二)——2-3-4树

  通过前面的介绍,我们知道在二叉树中,每个节点只有一个数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树。本篇博客我们将介...

3317
来自专栏Java 源码分析

平衡搜索树

2-3树 ​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子...

2879
来自专栏机器学习算法全栈工程师

红黑树算法

前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

36312

扫码关注云+社区