文档章节

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

猪刚烈
 猪刚烈
发布于 2014/10/12 11:47
字数 556
阅读 11
收藏 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在排序上的一个微妙的地方。

本文转载自:http://blog.csdn.net/bluishglc/article/details/20215565

共有 人打赏支持
猪刚烈
粉丝 22
博文 708
码字总数 110
作品 1
海淀
程序员
学习PriorityQueue源码

本来想先看看DelayQueue,结果里面用到了PriorityQueue,所以先学习一下PriorityQueue的编码逻辑。 基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序排序,或者由队列构造时提...

woshixin
10/10
0
0
基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

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

大数据之路
2013/06/02
0
0
Java PriorityQueue && PriorityBlockingQueue

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

秋风醉了
2015/01/12
0
0
优先级队列(PriprityQueue)是一种什么样的数据结构

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

pumpkinHua
2015/10/19
190
0
PriorityQueue源码分析

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

Hosee
2015/12/15
274
0

没有更多内容

加载失败,请刷新页面

加载更多

负载均衡的解决方案有哪些

负载均衡器服务可满足大型组织的需求,支持所有数据中心和跨数据中心高可靠性场景。 本地负载均衡,通过附带或者未附带持久性覆盖选项,Incapsula支持各种负载均衡算法,以优化服务器之间的流...

上树的熊
30分钟前
3
0
Java实现在线打开word文档加盖印章/盖章/签名功能

前言: 我们知道,大型一点的OA办公系统都会有很多在线处理office办公文档的需求。其中有一点也基本绕不开,那就是为文档盖章或添加手写签名来保护文档,让被盖章的文档不再被编辑。 在Java中...

山里的红杏
38分钟前
5
0
js控制输入正负数,小数点后保留两位

//限制数字function clearNoNum(obj){ //修复第一个字符是小数点 的情况. if(obj.value !=''&& obj.value.substr(0,1) == '.'){ obj.value=""; } obj.value ...

一直在成长的程序猿
41分钟前
2
0
动态代理

具体场景 为了使代理类与被代理类对第三方有相同的函数,代理类与被代理类一般实现一个公共的interface,定义如下 public interface Subject { void rent(); void hello(String s)...

wuyiyi
44分钟前
2
0
时间字段

我们看看这几个数据库中(mysql、oracle和sqlserver)如何表示时间 mysql数据库:它们分别是 date、datetime、time、timestamp和year。date :“yyyy-mm-dd”格式表示的日期值 time :“hh:...

DemonsI
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部