优先级队列-顺序混乱

Question

我遇到了一个奇怪的问题，我的优先级队列首先打印最后一个创建的项目，然后按顺序打印其他所有项目。

我正在为我的计算机科学课做这个作业的一个版本。我们使用Java中内置的PriorityQueue。磁盘对象可以容纳1000000 KB的数据，如果磁盘具有最多的可用空间，则磁盘具有优先级。

在我的解决方案中，Disk 7是最新创建的，尽管优先级较低，但它还是打印在顶部。有人知道是什么原因造成的吗？

这是我的解决方案：

public static void findWorstFit(String fileName) throws FileNotFoundException {
PriorityQueue<Disk> disks = new PriorityQueue<>();
double totalSize = 0;
// Process each file and add it to a disk
Scanner fileScanner = new Scanner(new File(fileName));
while(fileScanner.hasNextInt()) {
int file = fileScanner.nextInt();
if(disks.size() > 0 && disks.peek().freeSpace >= file)
disks.peek().add(file);
else
disks.offer(new Disk(disks.size(), file));
totalSize += file;
}
// Print all the disks
System.out.println("Total size = " + totalSize/1000000 + " GB");
System.out.println("Disks req'd = " + disks.size());
while(!disks.isEmpty())
System.out.println(disks.poll());
}

以下是预期输出：

Total size  = 6.580996 GB
Disks req'd = 8
5 325754: 347661 326585 
0 227744: 420713 351543 
7 224009: 383972 392019 
4 190811: 324387 484802 
6 142051: 340190 263485 254274 
3 116563: 347560 204065 331812 
2 109806: 396295 230973 262926 
1  82266: 311011 286309 320414

这是实际输出：

Total size  = 6.580996 GB
Disks req'd = 8
7 224009: 383972 392019 
5 325754: 347661 326585 
0 227744: 420713 351543 
4 190811: 324387 484802 
6 142051: 340190 263485 254274 
3 116563: 347560 204065 331812 
2 109806: 396295 230973 262926 
1  82266: 311011 286309 320414

Answer 1

您没有提供Disk类的实现。我想这有一个比较器，所以自然顺序按照最大可用空间到最小可用空间的顺序对磁盘进行排序。

问题实际上是，您正在修改PriorityQueue中的一个元素，并期望队列为您重新排序元素，但不知道元素已经更改。

一个快速的解决方案是，每次您想要修改队列时，都要删除它的头部，然后将其重新插入队列中。

即

更换

if(disks.size() > 0 && disks.peek().freeSpace >= file)
disks.peek().add(file);
else
disks.offer(new Disk(disks.size(), file));

带有

if(disks.size() > 0 && disks.peek().freeSpace >= file) {
Disk toChange = disks.poll();
toChange.add(file);
disks.offer(toChange);
}
else
disks.offer(new Disk(disks.size(), file));

这将保持disks队列中元素的顺序。

Answer 2

在我看来，可能有两个错误。

1. 您在Disk中对Comparable的实现不正确
2. 这条线——disks.peek().add(file);是可疑的，它与第一种可能性有关。当将添加到队列或从队列中删除时，PriorityQueue中的元素将被排序。这里是已插入元素的更改状态，最终更改其优先级(取决于Comparable的实现(。但这不会改变它在队列中的顺序，即使它的优先级可能会改变