Смотреть () или не смотреть ()

Question

У меня есть пример использования PriorityQueue, который производит

3

1

1

1

5

0

Это код

import java.util.*;

class Someclass
{

public static class IntegerWr 
    implements Comparable<IntegerWr>
{
    Integer val;

    IntegerWr(Integer val)
    {
        this.val = val; 
    }

    public void change(Integer nval)
    { 
        this.val = nval;
    }

    @Override
    public int compareTo(IntegerWr iw)
    {
        return val.compareTo(iw.val);
    }
    @Override public String toString()
    {
        return ""+val;
    }
}
    public static void main (String[] args) 
    {
        PriorityQueue<IntegerWr> pq = new PriorityQueue<>();
        pq.add(new IntegerWr(3));
        System.out.println(pq.peek());
        IntegerWr iw1 = new IntegerWr(1);        
        pq.add(iw1);
        System.out.println(pq.peek());
        pq.add(new IntegerWr(4));
        System.out.println(pq.peek());
        pq.add(new IntegerWr(2));
        System.out.println(pq.peek()); //must output 1, and does so
        iw1.change(5);                 //change value of element that is actually on peek
        System.out.println(pq.peek()); //outputs 5 which is unexpected
        pq.add(new IntegerWr(0));
        System.out.println(pq.peek()); 
    }
}

Похоже, заказы PriorityQueue только на вставке. Какой метод использовать для получения фактического peek()?

Answer 1

PriorityQueue является реализацией очереди. Если мы посмотрим на интерфейс очереди, у него есть методы peek(), poll(), remove().

peek() Метод возвращает, но не удаляет заголовок очереди.

poll() Метод удаляет и возвращает начало очереди. То, какой именно элемент удаляется из очереди, является функцией политики упорядочения очереди.

import java.util.*;

class Someclass
{

public static class IntegerWr 
    implements Comparable<IntegerWr>
{
    Integer val;

    IntegerWr(Integer val)
    {
        this.val = val; 
    }

    public void change(Integer nval)
    { 
        this.val = nval;
    }

    @Override
    public int compareTo(IntegerWr iw)
    {
        return val.compareTo(iw.val);
    }
    @Override public String toString()
    {
        return ""+val;
    }
}
    public static void main (String[] args) 
    {
        PriorityQueue<IntegerWr> pq = new PriorityQueue<>();
        pq.add(new IntegerWr(3));
        System.out.println(pq.peek());
        IntegerWr iw1 = new IntegerWr(1);        
        pq.add(iw1);
        System.out.println(pq.peek());
        pq.add(new IntegerWr(4));
        System.out.println(pq.peek());
        pq.add(new IntegerWr(2));
        System.out.println(pq.peek()); //must output 1, and does so
        iw1.change(5);                 //change value of element that is actually on peek
        System.out.println(pq.peek()); //outputs 5 which is unexpected
        pq.add(new IntegerWr(0));
        System.out.println(pq.peek()); 

        System.out.println("Elements ordered");
        Object o = null;
        while ((o = pq.poll()) != null) //poll() method removes and return
                                        //the head of the queue.
                                        //Exactly which element is removed 
                                        //from the queue is a function 
                                        //of the queue's ordering policy
        {
            System.out.println(o);
        }
    }
}

Выход

3

1

1

1

5

0

Elements ordered

0

2

3

4

5

Чтобы получить элементы PriorityQueue в порядке использования poll(),

Answer 2

Вместо iw1.change(5); делать:

pq.remove(iw1);
iw1.change(5);
pq.add(iw1);

Answer 3

Вы изменяете значение ВНУТРИ объекта, хранящегося в очереди. Очередь ничего не знает о содержимом объектов. Поэтому, когда вы вызываете метод для объекта в очереди (как в 'iw1.change(5)'), ничего в очереди не знает об этом. Вам нужно сохранить замещающий объект, чтобы в очереди переупорядочивать элементы.