使用自定义比较器在 O(n) 中创建 PriorityQueue
create PriorityQueue in O(n ) with custom comparator
我试图用带有自定义比较器的 Priorityqueue 实现 MST,但我在 O(n) 时间内用它构建最小堆时遇到问题。问题是只有一个 Priorityqueue 的构造函数允许在 O(n) 中创建 PriorityQueue,但它不接受任何比较器作为参数。我希望它使用我的自定义比较器。这个问题有解决方法吗? PriorityQueue.addAll() 将失去使用最小堆进行 MST 的目的,因为它是 O(nlogn) 方法。这是我的代码。
ArrayList <edge>ar=new ArrayList<>();
for(int i=0;i<e;i++)
{
int u=ss.nextInt();
int v=ss.nextInt();
int w=ss.nextInt();
ar.add(new edge(u,v,w));
}
PriorityQueue <edge>pr=new PriorityQueue<edge>(ar);
以及我想使用的比较器:-
PriorityQueue <edge>ar=new PriorityQueue(11,new Comparator() {
@Override
public int compare(Object o1, Object o2) {
edge n1=(edge) o1;
edge n2=(edge) o2;
if(n1.w<n2.w)
{
return -1;
}
else if(n1.w==n2.w)
{
if((n1.u+n1.v+n1.w)<=(n2.u+n2.v+n2.w))
{
return -1;
}
else
{
return 1;
}
}
else
{
return 1;
}
}
});
如果您没有在其他地方对您的列表进行最小堆排序,您将无法 new PriorityQueue(...)
任何事情并且以某种方式避免创建您的堆。数学 here 表示一般情况下是 O(n)
,但它仍然不仅仅是迭代。
PriorityQueue<edge> pr = new PriorityQueue<edge>(ar, comp) {
PriorityQueue(List<edge> ar, Comparator<edge> c) {
this(c);
for(int i = 0; i < queue.length; i++) {
queue[i] = ar.get(i);
}
this.size = queue.length;
heapify(); // O(n), except that heapify is private and thus you can't call it!!!
}
}
现在我还没有测试过这个,它只是在 PriorityQueue 源的一些指导下浮出水面,但它应该为您指明正确的方向。
但有时您必须付钱给吹笛者并创建堆顺序,而这不仅仅是迭代。不过,由于 heapify
,它应该仍然在 O(n)
上。
另一种选择是 edge
实施 Comparable<edge>
。那么你可以 PriorityQueue<edge> pr = new PriorityQueue(ar);
如果你无法控制edge implements Comparable<edge>
那么你可以组成一个容器class:
class EdgeContainer implements Comparable<EdgeContainer> {
private static final Comparator<edge> comp = ; // that comparator above
private final edge edge;
EdgeContainer(Edge edge) { this.edge = edge; }
public int compareTo(EdgeContainer e) { return comp.compare(edge, e.edge); }
public edge getEdge() { return edge; }
}
List <EdgeContainer>ar=new ArrayList<>();
for(int i=0;i<e;i++)
{
int u=ss.nextInt();
int v=ss.nextInt();
int w=ss.nextInt();
ar.add(new EdgeContainer(new edge(u,v,w)));
}
PriorityQueue<EdgeContainer> qr = new PriorityQueue(ar);
Java 的 PriorityQueue
需要 O(n) 时间从传递给它的集合中创建优先级队列。数学证明已在 CLSR 第 6.4 章(第 3 版第 157 页)中给出。直观地,当使用 siftDown
或 siftUp
将底层数组突变为堆时,为下一个 sift
操作循环的元素数量的大小也会减少,从而导致 O (n) 时间复杂度。
但是正如评论中所讨论的以及您在问题中提到的那样,您无法通过使用 addAll()
来实现此时间复杂度。原因是 adAll()
继承自 AbstractQueue
并且通过将集合中的元素一个一个地添加到队列中来工作,这会导致 O(nlogn) 时间复杂度。
因此,如果绝对需要 O(n) 时间复杂度,您将别无选择,只能为集合中包含的 class 个对象实现 Comparator
接口。 @corsiKa 的回答很好地详细说明了这种方法。另请注意,即使您将集合直接传递给 PriorityQueue
,它也会将其转换为数组,这基本上是另一个 O(n) 操作。
我试图用带有自定义比较器的 Priorityqueue 实现 MST,但我在 O(n) 时间内用它构建最小堆时遇到问题。问题是只有一个 Priorityqueue 的构造函数允许在 O(n) 中创建 PriorityQueue,但它不接受任何比较器作为参数。我希望它使用我的自定义比较器。这个问题有解决方法吗? PriorityQueue.addAll() 将失去使用最小堆进行 MST 的目的,因为它是 O(nlogn) 方法。这是我的代码。
ArrayList <edge>ar=new ArrayList<>();
for(int i=0;i<e;i++)
{
int u=ss.nextInt();
int v=ss.nextInt();
int w=ss.nextInt();
ar.add(new edge(u,v,w));
}
PriorityQueue <edge>pr=new PriorityQueue<edge>(ar);
以及我想使用的比较器:-
PriorityQueue <edge>ar=new PriorityQueue(11,new Comparator() {
@Override
public int compare(Object o1, Object o2) {
edge n1=(edge) o1;
edge n2=(edge) o2;
if(n1.w<n2.w)
{
return -1;
}
else if(n1.w==n2.w)
{
if((n1.u+n1.v+n1.w)<=(n2.u+n2.v+n2.w))
{
return -1;
}
else
{
return 1;
}
}
else
{
return 1;
}
}
});
如果您没有在其他地方对您的列表进行最小堆排序,您将无法 new PriorityQueue(...)
任何事情并且以某种方式避免创建您的堆。数学 here 表示一般情况下是 O(n)
,但它仍然不仅仅是迭代。
PriorityQueue<edge> pr = new PriorityQueue<edge>(ar, comp) {
PriorityQueue(List<edge> ar, Comparator<edge> c) {
this(c);
for(int i = 0; i < queue.length; i++) {
queue[i] = ar.get(i);
}
this.size = queue.length;
heapify(); // O(n), except that heapify is private and thus you can't call it!!!
}
}
现在我还没有测试过这个,它只是在 PriorityQueue 源的一些指导下浮出水面,但它应该为您指明正确的方向。
但有时您必须付钱给吹笛者并创建堆顺序,而这不仅仅是迭代。不过,由于 heapify
,它应该仍然在 O(n)
上。
另一种选择是 edge
实施 Comparable<edge>
。那么你可以 PriorityQueue<edge> pr = new PriorityQueue(ar);
如果你无法控制edge implements Comparable<edge>
那么你可以组成一个容器class:
class EdgeContainer implements Comparable<EdgeContainer> {
private static final Comparator<edge> comp = ; // that comparator above
private final edge edge;
EdgeContainer(Edge edge) { this.edge = edge; }
public int compareTo(EdgeContainer e) { return comp.compare(edge, e.edge); }
public edge getEdge() { return edge; }
}
List <EdgeContainer>ar=new ArrayList<>();
for(int i=0;i<e;i++)
{
int u=ss.nextInt();
int v=ss.nextInt();
int w=ss.nextInt();
ar.add(new EdgeContainer(new edge(u,v,w)));
}
PriorityQueue<EdgeContainer> qr = new PriorityQueue(ar);
Java 的 PriorityQueue
需要 O(n) 时间从传递给它的集合中创建优先级队列。数学证明已在 CLSR 第 6.4 章(第 3 版第 157 页)中给出。直观地,当使用 siftDown
或 siftUp
将底层数组突变为堆时,为下一个 sift
操作循环的元素数量的大小也会减少,从而导致 O (n) 时间复杂度。
但是正如评论中所讨论的以及您在问题中提到的那样,您无法通过使用 addAll()
来实现此时间复杂度。原因是 adAll()
继承自 AbstractQueue
并且通过将集合中的元素一个一个地添加到队列中来工作,这会导致 O(nlogn) 时间复杂度。
因此,如果绝对需要 O(n) 时间复杂度,您将别无选择,只能为集合中包含的 class 个对象实现 Comparator
接口。 @corsiKa 的回答很好地详细说明了这种方法。另请注意,即使您将集合直接传递给 PriorityQueue
,它也会将其转换为数组,这基本上是另一个 O(n) 操作。