I'm having a weird issue where my priority queue prints the last created item first, and then prints everything else in order.

I am working on a version of this assignment for my computer science class. We are using the in-built PriorityQueue in Java. A Disk object can hold 1,000,000 KB of data and a disk has priority if it has the most free space.

In my solution, Disk 7 was created latest, and it is printed on top despite the lower priority. Does anyone know what might be causing this?

Here is my solution:

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());
}

Here is the expected output:

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

And here is the actual output:

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

CodePudding user response：

You don't provide the implementation of the Disk class. I presume this has a comparator so the natural ordering sorts the Disks in order of most free space to least free space.

The issue is really that you are modifying an element within the PriorityQueue - and expecting the queue to reorder the elements for you - but it has no concept that the elements have been changed.

A quick fix would be to remove the head of the queue each time you want to modify it and re-insert it into the queue.

i.e.

replace

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

with

        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));

That would maintain the ordering of the elements within the disks queue.

CodePudding user response：

As i see it, there are two possible errors.

1. Your implementation of Comparable in Disk is incorrect.
2. This line - disks.peek().add(file); is fishy, it's connected to the first possibility. Elements in PriorityQueue are being ordered when adding to the queue or removing from it. Here you are the changing state of already inserted element, eventually changing its priority(depends on Comparable implementation). But this will not change its ordering in the queue, even though its priority might change.