Priority Queue - Order Messed Up

66
July 04, 2022, at 03:40 AM

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
Answer 1

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.

Answer 2

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.
Rent Charter Buses Company
READ ALSO
jMonkeyEngine dependencies with Gradle

jMonkeyEngine dependencies with Gradle

I am currently trying to implement a game written in java using jMonkey Graphic engineMy question is if it is possibile to load all the dependencies needed through Gradle, avoiding all *

102
package com.sun.beans.finder does not exist openjdk

package com.sun.beans.finder does not exist openjdk

When a file is compiled that imports comsun

114
Why does the JScrollPane show up but not its scroll bar? [duplicate]

Why does the JScrollPane show up but not its scroll bar? [duplicate]

Here is my codeThe JScrollpanel shows up but now the scrollbar

91
How to split a string containing date and words?

How to split a string containing date and words?

I have a bunch of string in the format "02-01-2014 10:02:01:001 abcd efgh" If I want to split it as ["02-01-2014 10:02:01:001", "abcd efgh"], how do I do that?

99