Java的PriorityQueue是不稳定的还是不确定的?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java的PriorityQueue是不稳定的还是不确定的?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2278字,纯文字阅读大概需要4分钟。
内容图文
![Java的PriorityQueue是不稳定的还是不确定的?](/upload/InfoBanner/zyjiaocheng/669/d701d129b97844fab4d95f1f858c0c9a.jpg)
我正在遍历Java的PriorityQueue文档,并遇到了一个重要注意事项:
If multiple elements are tied for least value, the head is one of
those elements — ties are broken arbitrarily
我想了解该粗体字的实际含义.我感兴趣的两个属性是PriorityQueue的稳定性及其确定性.
据我了解,稳定的算法将(摘自维基百科):
preserve the original order of the input set
而确定性算法将(摘自维基百科):
given a particular input, […] produce the same output
这是我的示例:
public class PriorityQueueTest {
public static class Herp implements Comparable<Herp>{
int attribute;
String name;
Herp(int attribute,String name){
this.attribute=attribute;
this.name=name;
}
@Override
public String toString(){
return name+": "+attribute;
}
@Override
public int compareTo(Herp o) {
return Integer.compare(o.attribute, this.attribute);
}
}
public static void main(String[] args){
PriorityQueue<Herp> queue= new PriorityQueue<Herp>();
queue.add(new Herp(1,"Fred"));
queue.add(new Herp(1,"James"));
queue.add(new Herp(2,"Bob"));
queue.add(new Herp(3,"Rachel"));
queue.add(new Herp(4,"Constance"));
List<Herp> debug= new ArrayList<>();
while(!queue.isEmpty()){
debug.add(queue.poll());
}
System.out.println(Arrays.toString(debug.toArray()));
}
}
对我来说,这段代码输出以下内容:
[Constance: 4, Rachel: 3, Bob: 2, Fred: 1, James: 1]
如果我切换弗雷德和詹姆斯的插入顺序,我会得到相同的结果.因此PriorityQueue不稳定.但是,我不能反驳其确定性.无论我尝试哪种插入顺序,无论我运行了多少次代码,Fred总是排在James之前.
但是,我担心这种行为是特定于计算机或JVM的(在我看来,这是不确定的),或者存在一些反例,其输出将有所不同.
另一个可能性是,尽管目前在所有JVM和计算机上的实现可能是确定性的,但未指定此属性,并且将来可能会对其进行更改.
我可以理解内部实现是否基于某种ObjectID或内部内存值打破了束缚,这将使其变得不稳定但具有确定性.但是,它也可以根据系统时间,随机数,月相等来进行.这将使其变得不稳定且不确定.
TLDR:Java的PriorityQueue是否具有确定性?
This question尽管有其名称,但证明了该算法的不稳定性,其答案仅与文档有关,而文档未对确定性做出回应.
解决方法:
它不是稳定的:领带是否被任意打破不可能.这意味着实现可以自由选择要首先返回的任何绑定元素.一个稳定的实现必须按绑定元素插入队列的顺序返回它们.
它不一定是确定性的或不确定性的:它可以选择如何任意打破平局,因此它可以确定性地进行操作(即,如果您放入相同的元素,则可以按相同的顺序将它们取出来,不论该顺序是什么)或不确定的方式(即,相同的元素不会以相同的顺序出现).
内容总结
以上是互联网集市为您收集整理的Java的PriorityQueue是不稳定的还是不确定的?全部内容,希望文章能够帮你解决Java的PriorityQueue是不稳定的还是不确定的?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。