CODEWITHSUNDEEP
javacollectionspriority-queuepeek
Developer Marius Žilėnas
Developer Marius Žilėnas

Reputation: 6119

To peek() or not to peek()

I have PriorityQueue use example which produces

3

1

1

1

5

0

This is the code

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

Seems like the PriorityQueue orders only on insert. What method to use to get the actual peek()?

Upvotes: 0

Views: 955

Answers (3)

Developer Marius Žilėnas
Developer Marius Žilėnas

Reputation: 6119

PriorityQueue is an implementation of the Queue. If we look at the Queue interface it has methods peek(), poll(), remove().

peek() method returns, but does not remove, the head of the queue.

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.

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

Output

3

1

1

1

5

0

Elements ordered

0

2

3

4

5

To get elements of PriorityQueue in order use poll().

Upvotes: 0

Anonymous
Anonymous

Reputation: 86333

Instead of iw1.change(5); do:

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

Upvotes: 1

jr593
jr593

Reputation: 277

You are changing a value INSIDE the object stored in the queue. The queue does not know anything about the contents of the objects. So when you call a method on an object in the queue (as in 'iw1.change(5)'), nothing in the queue knows about it. You need to store a replacement object, for the queue to re-order the elements.

Upvotes: 1

Related Questions