Приоритетная очередь в Java - получение определенного элемента

Question

У меня есть очередь приоритетов, содержащая элементы настраиваемого типа, называемого Process. Каждый процесс имеет 3 поля. Мне нужно иметь возможность получить Process из моей очереди приоритетов, которая имеет определенное значение для одного из своих полей. Как я могу это сделать? Кажется, что poll() всегда возвращает голову очереди.

Вот мой код класса Process:

package SPN; 

public class Process implements Comparable<Process> { 

    @Override 
    public int compareTo(Process proc) { 
     //implement this 
     return 0; 
    } 

    private int arrive_time= 0; 
    private int burst_time = 0; 
    private int remain_time = 0; 

    public Process (int arr_time, int bur_time) { 

     this.arrive_time = arr_time; 
     this.burst_time = bur_time; 
    } 

    public int getArrTime() {return arrive_time;} 
    public int getBurTime() {return burst_time;} 
    public int getRemTime() {return remain_time;} 
} 

В другом классе я создал очереди приоритетов под названием PRQ и добавлены процессы с разными значениями полей. Не беспокойтесь о неполном коде. Я просто не могу добавить все, потому что это будут страницы кода. Что-то вроде этого:

p1 = new Process(2, 10); 
prq.add(p1); 

p2 = new Process(1, 8); 
prq.add(p2); 

p3 = new Process(0, 11); 
prq.add(p3); 

Мне нужно, чтобы иметь возможность получить процесс p3, поскольку она имеет самый ранний arrive_time. Как я могу это сделать? Кажется, что восстанавливается и удаляется только глава очереди приоритетов. Не рекомендуйте использовать другую структуру данных, так как это не работает. Должна быть очередью приоритетов, потому что мне нужно сделать дополнительный выбор на основе других полей.

Process current = prq.poll(); 

Answer 1

Вы должны реализовать compareTo метод, как это:

@Override 
public int compareTo(Process proc) { 
    // this.arriveTime > proc.arriveTime --> >0 
    // this.arriveTime < proc.arriveTime --> <0 
    // this.arriveTime = proc.arriveTime --> 0 
    return this.arriveTime - proc.arriveTime; 
} 

Таким образом, элементы, которые имеют меньше arriveTime придет первым.

Answer 2

Причина, по которой я вижу здесь, состоит в том, что у вас есть незавершенная реализация метода compareTo() в классе Process. Поскольку возвращаемый всегда нуль возвращается, поиск происходит в порядке вставки, поскольку он рассматривает каждый объект равным.

Вы могли бы завершить реализацию, как показано ниже

public void compareTo(Process proc) 
{ 
    if (this.getArrTime() < proc.getArrTime()) { 
     return -1; 
    else if (this.getArrTime() > proc.getArrTime()) { 
     return 1; 
    else 
     return 0; 
} 

Answer 3

Это не является необходимым для Process класса для реализации Comparable<Process> интерфейса:

public class Process { 
    private int arrive_time= 0; 
    private int burst_time = 0; 
    private int remain_time = 0; 

    public Process (int arr_time, int bur_time) { 
     this.arrive_time = arr_time; 
     this.burst_time = bur_time; 
    } 

    public int getArrTime() {return arrive_time;} 
    public int getBurTime() {return burst_time;} 
    public int getRemTime() {return remain_time;} 
} 

Ваш PriorityQueue, который назван prq может быть инициализирован, как:

PriorityQueue<Process> prq = new PriorityQueue<Process>(new Comparator<Process>() { 
    // arrive_time in ascending order 
    @Override 
    public int compare(Process p1, Process p2) { 
     return p1.arrive_time - p2.arrive_time; 
    } 
}); 

Тогда:

Process p1 = new Process(2, 10); 
    prq.add(p1); 

    Process p2 = new Process(1, 8); 
    prq.add(p2); 

    Process p3 = new Process(0, 11); 
    prq.add(p3); 

    System.out.println(prq.poll().getArrTime()); // output is 0 (which means p3) 
    System.out.println(prq.poll().getArrTime()); // output is 1 (which means p2) 

Answer 4

Назначение PriorityQueue должен иметь набор элементов, отсортированных по их приоритету. В вашем случае приоритеты имеют процессы, которые пришли раньше. При добавлении элемента в PriorityQueue он будет сравниваться с другими элементами, которые уже находятся в очереди и помещены в нужное место.

Теперь я чувствую, что мы все еще немного неясны в сравнении объектов, поэтому вот несколько пояснений к этому: Метод сравнения (который вы должны реализовать из-за интерфейса Comparator) всегда возвращает значение int, то есть либо < 0, равным 0 или> 0.

• равно 0 означает, что два значения по сравнению равны друг другу
• > 0 означает, что это «больше», чем объект данного в качестве параметра
• < 0 означает, что это «меньше» чем объект, заданный как параметр

Теперь, как я уже упоминал, очередь будет сравнивать значение, которое вы пытаетесь вставить, в значения, которые уже находятся в очереди, в соответствии с вашим методом сравнения.

Итак, все, что вам нужно сделать, это правильно реализовать свой метод сравнения, как объяснил Кирилл Александров.

Обратитесь к Oracle Docs https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html