优先队列 - 顺序混乱

Question

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

我正在为我的计算机科学 class 编写 this 作业。我们在 Java 中使用内置的 PriorityQueue。一个磁盘对象可以容纳 1,000,000 KB 的数据，如果磁盘具有最多的空闲空间，则该磁盘具有优先权 space。

在我的解决方案中，磁盘 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

您没有提供磁盘 class 的实现。我认为这有一个比较器，因此自然顺序按最空闲 space 到最空闲 space.

的顺序对磁盘进行排序

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

一个快速的解决办法是每次你想修改它时删除队列的头部，然后re-insert它进入队列。

即

替换

        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

据我所知，有两个可能的错误。

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

优先队列 - 顺序混乱

Priority Queue - Order Messed Up

java

priority-queue