文档章节

使用PriorityQueue排序?结果可能不是你想要的

猪刚烈
 猪刚烈
发布于 2014/10/12 11:47
字数 556
阅读 11
收藏 0
点赞 0
评论 0

PriorityQueue有一个特征需要特别注意,即:对于那些通过排序方法判定为“相等”的元素,在通过poll方法依次取出它们时,它们的顺序是不确定的,特别是不会维持插入的顺序。举例说明:假如一个对象Obj,有a,b两个字段,如果Obj对象是按字段a由小到大进行排序的,当向队列依次插入a,b分别为:(1,1),(2,1),(1,2),(2,2),(1,3)的五个元素时,通过poll方法从队头依次取出的元素会是什么呢?首先,一定可以确定的是(1,1),(1,2),(1,3)一定会排在前面,(2,1),(2,2)一定会排在后面,问题在于(1,1),(1,2),(1,3)之间和(2,1),(2,2)之间是如果排序的,习惯上我们希望它们保留插入时的顺序,但是实际上,在PriorityQueue在进行内部排序时,它们的原始插入顺序都被破坏了,所以实际的输出时,相等元素之间的顺序是不确定的。以下是一段验证程序:

import java.util.*;

public class Test1 {
    public static void main(String[] args) {
        PriorityQueue<Obj> q = new PriorityQueue<Obj>();
        q.add(new Obj(1,1));
        q.add(new Obj(2,1));
        q.add(new Obj(1,2));
        q.add(new Obj(2,2));
        q.add(new Obj(1,3));
        int size = q.size();
        for (int i = 0; i < size; i++) {
            System.out.println(q.poll());
        }
        System.out.println("--------------------------");
        List<Obj> l = new ArrayList<Obj>();
        l.add(new Obj(1, 1));
        l.add(new Obj(2, 1));
        l.add(new Obj(1, 2));
        l.add(new Obj(2, 2));
        l.add(new Obj(1, 3));
        Collections.sort(l);
        for (Obj obj : l) {
            System.out.println(obj);
        }
    }
    public static class Obj implements Comparable<Obj> {
        int a;
        int b;
        public Obj(int a, int b) {
            this.a = a;
            this.b = b;
        }
        @Override
        public String toString() {
            return "Obj{" +
                    "a=" + a +
                    ", b=" + b +
                    '}';
        }

        @Override
        public int compareTo(Obj o) {
            return a - o.getA();
        }
        public int getA() {
            return a;
        }
        public void setA(int a) {
            this.a = a;
        }
        public int getB() {
            return b;
        }
        public void setB(int b) {
            this.b = b;
        }
    }
}

程序的输出是:

Obj{a=1, b=1}
Obj{a=1, b=3}
Obj{a=1, b=2}
Obj{a=2, b=2}
Obj{a=2, b=1}
--------------------------
Obj{a=1, b=1}
Obj{a=1, b=2}
Obj{a=1, b=3}
Obj{a=2, b=1}
Obj{a=2, b=2}

请注意前半段使用PriorityQueue,(1,1),(1,2),(1,3)三者的实际顺序是:(1,1),(1,3),(1,2)。 而使用排序方法排序得到的是我们期望的顺序。这就是PriorityQueue在排序上的一个微妙的地方。

© 著作权归作者所有

共有 人打赏支持
猪刚烈
粉丝 22
博文 708
码字总数 110
作品 1
海淀
程序员
基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具...

xrzs ⋅ 2013/06/02 ⋅ 0

Java PriorityQueue && PriorityBlockingQueue

Java PriorityQueue && PriorityBlockingQueue 我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时...

秋风醉了 ⋅ 2015/01/12 ⋅ 0

优先级队列(PriprityQueue)是一种什么样的数据结构

优先级队列(PriprityQueue)是一种无界队列,基于优先级堆,它的元素根据自然顺序或者通过实现Comparator接口的自定义排序方式进行排序。这篇文章,我们将创建一个Items的优先级队列,基于价...

pumpkinHua ⋅ 2015/10/19 ⋅ 0

PriorityQueue源码分析

PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如...

Hosee ⋅ 2015/12/15 ⋅ 0

出现次数较多的k个数 Top K Frequent Words

问题: Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequen......

叶枫啦啦 ⋅ 02/01 ⋅ 0

Java优先队列(PriorityQueue)示例

我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时段生成股票报告的应用程序,需要处理大量数据并...

wx5955e325d6bfb ⋅ 2017/07/04 ⋅ 0

Java中的优先级队列(一)

优先级队列的介绍 优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。...

peanutmain ⋅ 2016/11/20 ⋅ 0

数据库中间件 Sharding-JDBC 源码分析 —— 结果归并

摘要: 原创出处 www.iocoder.cn/Sharding-JD… 「芋道源码」欢迎转载,保留摘要,谢谢! 本文主要基于 Sharding-JDBC 1.5.0 正式版 1. 概述 2. MergeEngine 2.1 SelectStatement#setIndexFor...

芋道源码掘金Java群217878901 ⋅ 2017/10/29 ⋅ 0

猎头最爱问的java面试题附答案(三)

1.你了解大O符号(big-O notation)么?你能给出不同数据结构的例子么? 大O符号描述了当数据结构里面的元素增加的时候,算法的规模或者是性能在最坏的场景下有多么好。 大O符号也可用来描述其...

嘿你好夏天 ⋅ 2017/12/30 ⋅ 0

java中queue的使用

Queue接口与List、Set同一级别,都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问...

binhu ⋅ 2016/07/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 27分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 39分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 今天 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部