2 qianheshang qianheshang 于 2016.03.29 12:40 提问

java中的优先队列PriorityQueue不再维护最小优先是怎么回事

用最小优先队列实现Dijkstra算法出现PriorityQueue不再维护最小优先,从队列中弹出一个结点后,队列中其余结点顺序未发生改变,
导致第一个元素不是最小值

2个回答

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.03.29 13:32

根据API说明,这个类的队列首元素是最小的啊。你是怎么使用这个类的呢?

 <p>The <em>head</em> of this queue is the <em>least</em> element with respect to the specified ordering. 
wojiushiwo945you
wojiushiwo945you 回复qianheshang: 我看源码了它是根据传入元素实现Comparable接口指定排序操作的。可能跟你的Node的比较实现有关。
2 年多之前 回复
qianheshang
qianheshang public static int[] dijkstra(Node[] node, Node n, int[][] e) { //n为起始点 n.d = 0; PriorityQueue<Node> pn = new PriorityQueue<Node>(); for (int i = 0; i < node.length; i++) { if (node[i] == null) { break; } pn.add(node[i]); } int[] s = new int[pn.size()]; while (pn.size() != 0) { Node u = pn.peek(); Node v = u.next; while (v != null) { relax(u, node[v.id], e[u.id][v.id]); s[v.id] = node[v.id].d; v = v.next; } pn.poll(); } return s; }
2 年多之前 回复
qianheshang
qianheshang   2016.03.29 13:59

public static int[] dijkstra(Node[] node, Node n, int[][] e) {
//n为起始点
n.d = 0;
PriorityQueue pn = new PriorityQueue();
for (int i = 0; i < node.length; i++) {
if (node[i] == null) {
break;
}
pn.add(node[i]);
}
int[] s = new int[pn.size()];
while (pn.size() != 0) {
Node u = pn.peek();
Node v = u.next;
while (v != null) {
relax(u, node[v.id], e[u.id][v.id]);
s[v.id] = node[v.id].d;
v = v.next;
}
pn.poll();
}
return s;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
java/scala优先队列(PriorityQueue)元素改变后如何实现有序
java PriorityQueue能够对加入的元素按元素(必须是可比较的Comparable)大小排序,从而出队时总是“最小”元素优先出对。然而,现实应用中存在队列从元素发生改变的情况,PriorityQueue其实并不能时刻保证元素是有序。PriorityQueue在add addAll后会进行元素重排序,其余操作不会触发元素重排序。class AB{ AB(int a int
java中(优先队列)PriorityQueue的使用
import java.util.*; public class test1 { public static void PrintPr(Queue queue){ while(queue.peek()!=null){ System.out.print(queue.remove()+" "); } System.out.println(); } public stat
Python 标准库 —— 队列(Queue,优先队列 PriorityQueue)
优先队列,有别于普通队列的先入先出(虽然字面上还是队列,但其实无论从含义还是实现上,和普通队列都有很大的区别),也有别于栈的先入后出。在实现上,它一般通过堆这一数据结构,而堆其实是一种完全二叉树,它会对进入容器的元素进行排序(根据事先指定的规则),出队的顺序则会是二叉树的根结点代表的元素。 1. 接口介绍import Queueclass ComparableObj:
python 堆和优先队列的使用
1.heapqpython里面的堆是通过在列表中维护堆的性质实现的。这一点与C++中heap一系列的算法类似,底层是通过堆vector的维护获取堆的性质。 python堆的部分API,其他API查阅文档python_heap_API和 heapq的源代码import heapq #向堆中插入元素,heapq会维护列表heap中的元素保持堆的性质 heapq.heappush(heap, item
PriorityQueue+Dijkstra优先队列优化的Dijkstra
前面分别介绍了“原生的Dijkstra”即毫无优化的Dijkstra,但这种Dijkstra的效率较低为n^n,因此面对较大数据量的时候需要对其进行优化,也就是优化所采用的贪心策略的实现,因此就有了Heao+Dijkstra堆优化的Dijkstra,但是堆优化的实现很复杂,而PriorityQueue+Dijkstra优先队列优化的Dijstra的效率虽然略低于堆优化的Dijkstra,但是实现却容易的多,也不容易出错,因为可以借助java类库中的PriorityQueue来实现,因此优先队列优化的Dijk
用 C# 实现优先队列
优先队列(priority queue) 是很重要的数据结构。我在做 ACM 题时就经常要用到她。C++ STL 就包括 priority_queue 。Java 也有 PriorityQueue 类。遗憾的是,.NET Framework Base Class Library 中并不包括优先队列。于是,我只好自己用 C# 语言写一个,如下所示: using System; using Sy
索引式优先队列(indexed priority queue)
为了达到O(ElogV)的效率,需要对普利姆算法进行eager实现。 如果我们用java来做,jdk当中的priorityQueue并不能满足我们的要求。 因为我们需要进行一个对索引元素降key的操作(decrease-key)./** * 将索引所关联的key降到newKey * * @param index 索引 * @param newKey 新的k
JDK源码研究PriorityQueue(优先队列)
Priority Queue   目的: 通过对JDK源码的分析,进一步了解堆和优先队列,体会JDK源码的优美之处。 目录:         1:概念         2:源码结构         3:方法分析 概念: 概念1:堆 堆,n个关键字序列K1,K2,…,Kn,当且仅当该序列满足如下性质称为堆 ki≤K2i且ki≤K2i+1(最小堆) 或 (2)Ki≥K2i且ki≥
[C++ 实现最大值优先队列和最小值优先队列]
使用priority_queue容器适配器所有操作函数,实现最大值优先队列和最小值优先队列#include <iostream> #include <queue> #include <algorithm> #include <iterator> #include <vector> #include <functional>using namespace std; void main() {
PriorityQueue优先队列实现原理
一、什么是优先队列    优先队列不是按照普通对象先进先出原FIFO则进行数据操作,其中的元素有优先级属性,优先级高的元素先出队。本文提到的PriorityQueue队列,是基于最小堆原理实现。 二、什么是最小堆     最小堆是一个完全二叉树,所谓的完全二叉树是一种没有空节点的二叉树。     最小堆的完全二叉树有一个特性是根节点必定是最小节点,子女节点一定大于其父节点。还有一个