关于PriorityQueue不得不说的事

Question

写程序的时候，用多线程，想要实现根据线程中定义的一个权重值，来每次取出一个最小的，来操作。想来，貌似是优先级队列，因此就用PriorityQueue来实现咯
本来想偷懒，可惜写完测得时候就出问题了·~~
当然，也许是我对这个类不是很熟造成的疑问：1、PriorityQueue默认的排序是升序还是降序啊？
2、我在用PriorityQueue时，先new了一个实例，
PriorityQueue<TestThread> poolQueue=new PriorityQueue<TestThread>(5);
我想问下，这个对列能够使用自定义的Comparator？
3、我在向这个poolQueue中添加元素的时候~~~直接用的offer，所有new的TestThread的优先级初始都是一样的~~
可是我在offer第二个对象的时候就报错了·~~~
Exception in thread "main" java.lang.ClassCastException: TestThread cannot be cast to java.lang.Comparable
at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:595)
at java.util.PriorityQueue.siftUp(PriorityQueue.java:591)
at java.util.PriorityQueue.offer(PriorityQueue.java:291)
at cn.gov.cma.ncc.dcmpp.dispatch.server.util.PrioritySortUtil.main(PrioritySortUtil.java:58)
这错貌似是因为不能对对象直接排序，默认的Comparator不支持。第一次用这玩意·~~不太会，在此开贴求教！！

Answer 1

1、升序
2、可以，new PriorityQueue(5, new MyComparator());
3、因为你的对象没有实现Comparable或者传入Comparator

Answer 2

to ChDw
那个优先级队列是不是只能对线程使用啊？如果我在一个线程中定义了一个int值weight，这个值在该线程的运行过程中会不断地改变，
我循环new这个线程，并把它加入优先级队列队列指定Comparator为SortUtil编写的那个SortUtil主体代码为
int compare（MyThread fst，MyThread scd）{
//这里简单表示了一下~~
return (fst.getWeight()>=scd.getWeight)?1:-1
} 这个comparator我在单独测试的时候，用Collections.sort(arrList,new SortUtil())排序
是可以使用的·~~这样，我直接使用这个优先级队列·~·它能够根据我提供的对weight进行排序的筛选操作么？
这个队列每次追加对象的时候是用offer呢，还是用add啊？看了API我自己觉得add只是加到文件尾，不会自己排序，offer是插入~~~
可是在调用offer的是后形参对象应该用哪个？我是直接offer（MyThread），结果就是报错的·~我感觉这个地方我写的不对~~~应该怎么处理啊？
先谢谢你拉·~

Answer 3

PriorityQueue与线程没有什么关系，用在哪里都可以。
你说，队列指定Comparator为SortUtil，我不知道你怎么写的。
PriorityQueue<MyThread> q = new PriorityQueue<MyThread>(10, new Comparator<MyThread>() { public int compare(MyThread o1, MyThread o2) {
return o1.weight - o2.weight;
}

});
q.offer(new MyThread(5));
q.offer(new MyThread(7));
q.offer(new MyThread(2));
q.offer(new MyThread(6));
q.offer(new MyThread(8));
System.out.println(Arrays.toString(q.toArray()));
public static class MyThread {
private int weight;
public MyThread(int weight) {
this.weight = weight;
}

public String toString() {
return getClass().getSimpleName() + ":" + weight;
}
}
这个是很正常的。不会有异常。add和offer方法是一样的，没有任何区别。

Answer 4

to ChDw这个是我写的SortUtil.javapublic class SortUtil implements Comparator<MyThread> { /**
 * MAX:按照优先级从大到小排列
 * MIN:按照优先级从小到大排列(默认)
 */
public final static int MAX=-1;
public final static int MIN=1;
private int stat=0;
public SortUtil(){}
public SortUtil(int status){
stat=status;
}

public int compare(MyThread fst, MyThread scd) {
int ans = 0;
if (stat==MAX) {//从大到小
if (fst.getWeight()<=scd.getWeight()) {
return 1;
}else {
return -1;
}
}else if(stat==MIN||stat==0) {//从小到大
if (fst.getWeight()>=scd.getWeight()) {
return 1;
}else {
return -1;
}
}else {//模式选择错误
System.out.println("模式选择错误！");
System.exit(-2);
}
return ans;
}

/**
 * @param args
 */
public static void main(String[] args) {
//这段main函数里的是刚写的~~还没测~~~~
PriorityQueue<MyThread> pQueue=new PriorityQueue<MyThread>(5,new SortUtil());
for(int i=0;i<5;i++){
MyThread myT=new MyThread();
myT.start();
pQueue.offer(myT);
}

System.out.println(Arrays.toString(pQueue.toArray()));
}
}
这个是我写的MyThread里的run方法~~~~public void run() {

Calendar cur;
long n;
try {
while (true) {
cur=Calendar.getInstance();
n=cur.getTimeInMillis()/1000;
if (n%2==0) {
weight--;
}else {
weight++;
}
Thread.sleep(n);
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

}

Answer 5

改了下测试方法·~~~但是从输出看~~貌似队列里没有排序啊·~~~
这个队列会自动排序么?/**
 * @param args
 */
public static void main(String[] args) {
int cnt=0;
PriorityQueue<TaskThread> pQueue=new PriorityQueue<TaskThread>(5,new CopyOfSortUtil());
for(int i=0;i<5;i++){
TaskThread myT=new TaskThread();
myT.start();
pQueue.offer(myT);
}

System.out.println(Arrays.toString(pQueue.toArray()));
try {
while (cnt<5) {
while (!pQueue.isEmpty()) {
Thread.sleep(1000L);
TaskThread taskThread = pQueue.peek();
System.out.println(taskThread.getWeight());
}
cnt++;
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

Answer 6

巨汗·~~敲代码的时候有个符号搞错了~~害我看半天输出没找出来~~~~那个MyThread里的run方法的n=cur.getTimeInMillis()/1000;这句
应该改为n=cur.getTimeInMillis()%1000;现在问题是~~~貌似队列里面没有自动排序啊·~~要不就是我的测试方法还是不对
（测试方法里面的TaskThread等同其他地方的MyThread）

Answer 7

PriorityQueue内部成员数组queue其实是实现了一个二叉树的数据结构，因此它的排序其实是排序的二叉树，因此它的树的根即第一个元素都是最小的元素 当每次从PriorityQueue中取数据的时候，你会发现它后面几个元素的排序会变化的，而且都是有规律的PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("dog");
pq.add("apple");
pq.add("fox");
pq.add("easy");
pq.add("boy");
//
while(!pq.isEmpty()){
for(String s:pq){
System.out.print(s+" ");
}
System.out.println();
System.out.println("Priority.poll() : "+pq.poll());
}
结果:apple boy fox easy dog 
Priority.poll() : apple
boy dog fox easy 
Priority.poll() : boy
dog easy fox 
Priority.poll() : dog
easy fox 
Priority.poll() : easy
fox 
Priority.poll() : fox
从这段代码可以看出,第一个元素都是最小的，而每次取出一个数据的时候，后面几个元素都是变化的，而它们变化的规则就是根据二叉树的形式操作的（ps:具体的可以看看二叉树的相关知识）

Answer 8

也就是说·~在poll首个元素的时候~~pq才会根据二叉树重构对么？因为我的pq是在for循环里面添加元素的·~~
如果是 我倒序添加~~那会是什么情况呢？

Answer 9

无论你怎么顺序添加，PriorityQueue都会保证顺序取出的。这个你随便找个代码测试一下就行了（别用你自己的类，用什么String之类就非常清楚了）

Answer 10

你在多线程共享这个队列的情况下不能使用 PriorityQueue，而应该使用 PriorityBlockingQueue

Answer 11

PriorityQueue和PriorityBlockingQueue没用过，learning~~~

Answer 12

to ChDw  这样啊·~~那我还是自己用list实现吧·to OnlyLau  我记得这个Queue不是内部以堆的形式排列的么？
堆的话·~不是可以指定排序规范么？to bao110908  恩·~不过这个队列不是共享队列~~~只被一个线程持有~~~只不过·~~这个队列里存的是着多个线程的属性值~~~

Answer 13

ProirityQueue主要是用来做什么的呀？