将值添加到优先级队列时,何时对值进行排序?
考虑这个伪代码:将值添加到优先级队列时,何时对值进行排序?
PriorityQueue <Integer> pq = new PriorityQueue(new Comparator()
{
public int compare(Object o1, Object o2)
{
Integer e1 = (Integer)o1;
Integer e2 = (Integer)o2;
if (e1 > e2) {return -1;}
if (e2 > e1) {return 1;}
return 0;
}
});
pq.add(4);
pq.add(7);
pq.add(5);
pq.add(2);
pq.add(9);
现在我想知道,在运行时间什么时候确实队列运行compare()方法?我以为,它会按照这个顺序:
我)首先,数字4,7,5,2,9将被添加到队列的顺序
II)则优先级队列使用的比较方法排序的值
换句话说,该值被首先插入到队列中。然后他们被排序。这个想法是否正确?还是值被排序,因为他们被添加到队列?
PriorityQueues不类似种类排序数组的简单排序的数据结构。 Java中的PriorityQueue是使用优先级堆实现的。您应该了解堆是如何工作的,但基本上当您添加新元素时,会发生最大log(n)比较。没有必要比较所有元素。您可以在https://en.m.wikipedia.org/wiki/Priority_queue
只是一个小问题:什么是“回归1”的意义和“在compare()方法中返回-1“?它如何确定排序? – User95
@ User95我的解释是,它显示了'e2'和'e1'之间的区别。因此,例如说,如果'E2-E1> 0'则返回'1'否则如果'E2-E1 procrastinator
PriorityQueue
类了解更多关于优先级队列具有用于插入顺序(private final Comparator<? super E> comparator
)定义的私有字段Comparator
......所以,当你这样做:
PriorityQueue<Integer> pq = new PriorityQueue<>(foo);
其中foo是的一个实例比较器,该对象将在内部为该实例初始化...
在集合创建后,你开始添加元素,它和这里就是奇迹发生。
只看该PriorityQueue
类中,你会找到方法siftUpUsingComparator
,将被调用,并且使用定义来验证广告订单中的比较...
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
Offtopic:
你正在使用原始的收藏,这是不好的,我sugest调整你的代码类似于:
Comparator<Integer> foo = (o1, o2) -> {
Integer e1 = o1;
Integer e2 = o2;
if (e1 > e2) {
return -1;
}
if (e2 > e1) {
return 1;
}
return 0;
};
PriorityQueue<Integer> pq = new PriorityQueue<>(foo);
pq.add(4);
pq.add(7);
pq.add(5);
pq.add(2);
pq.add(9);
这是哪一种语言?你在用什么框架? –
对,我的坏。它是Java – User95
这些值必须在添加时排序。否则,队列应该如何知道你已经完成添加元素? – JimmyB