文档章节

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

猪刚烈
 猪刚烈
发布于 2014/10/12 11:47
字数 556
阅读 34
收藏 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
海淀
程序员
私信 提问
加载中
请先登录后再评论。
浅入浅出Android(003):使用TextView类构造文本控件

基础: TextView是无法供编辑的。 当我们新建一个项目MyTextView时候,默认的布局(/res/layout/activity_main.xml)中已经有了一个TextView: <TextView 运行效果如下: 修改其文本内容...

樂天
2014/03/22
708
1
CDH5: 使用parcels配置lzo

一、Parcel 部署步骤 1 下载: 首先需要下载 Parcel。下载完成后,Parcel 将驻留在 Cloudera Manager 主机的本地目录中。 2 分配: Parcel 下载后,将分配到群集中的所有主机上并解压缩。 3 激...

cloud-coder
2014/07/01
6.9K
1
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.5K
16
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
树莓派(Raspberry Pi):完美的家用服务器

自从树莓派发布后,所有在互联网上的网站为此激动人心的设备提供了很多有趣和具有挑战性的使用方法。虽然这些想法都很棒,但树莓派( RPi )最明显却又是最不吸引人的用处是:创建你的完美家用...

异次元
2013/11/09
7.7K
8

没有更多内容

加载失败,请刷新页面

加载更多

Subversion存储库中“分支”,“标记”和“主干”的含义是什么?

问题: I've seen these words a lot around Subversion (and I guess general repository) discussions. 我已经在Subversion(我猜通用存储库)讨论中看到了很多这样的话。 I have been us......

富含淀粉
今天
5
0
《Java8实战》笔记(03):Lambda表达式

本文源码 Lambda 管中窥豹 可以把Lambda表达式理解为简洁地表示可传递的匿名函数的一种方式:它没有名称,但它有参数列表、函数主体、返回类型,可能还有一个可以抛出的异常列表。 Lambda表达...

巨輪
今天
7
0
从其他文件夹导入文件 - Importing files from different folder

问题: I have the following folder structure. 我有以下文件夹结构。 application/app/folder/file.py and I want to import some functions from file.py in another Python file which r......

javail
今天
22
0
大数据研发学习之路--Hadoop集群搭建

阅读编译文档 准备一个hadoop源码包,我选择的hadoop版本是:hadoop-2.7.7-src.tar.gz,在hadoop-2.7.7的源码 包的根目录下有一个文档叫做BUILDING.txt,这其中说明了编译hadoop所需要的一些...

DSJ-shitou
今天
8
0
OSChina 周五乱弹 —— 特么是别的公司派来的特洛伊木马吧?

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐:《我会守在这里》- 毛不易 《我会守在这里》- 毛不易 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :股市连跪了五天,...

小小编辑
今天
77
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部