Problem with Priority Queue

Question

I'm trying to use a priority queue in my code, and for some reason when I remove the objects, they aren't in order. Do you know what i"m doing wrong? Here's my code:

the contructor:

recordedsong = new PriorityQueue<recordedNote>(50, new Comparator<recordedNote>()
        {
            public int compare(recordedNote n1, recordedNote n2)
            {
                long l = n1.rt()-n2.rt();
                int i = (int)l;
                return i;
            }
        });

where each recordedNotehas a long value that is returned my the method rt().

But when I call

while (!Song.isEmpty())
        {
            recordedNote temp = (recordedNote)Song.remove();

and then print temp.rt() for each one, all the numbers are out of order. And not just like reverse order, but all over the place, like 1103, 0, 500, 0, 220 orders like that.

Can you see if there's anything wrong with my contructor?

Thanks!

are you using add() or offer() to insert into the queue? — Joe Phillips
– Joe Phillips, Commented Feb 8, 2011 at 4:08
What is Song by the way? I don't see it as a declared variable or class. — Hovercraft Full Of Eels
– Hovercraft Full Of Eels, Commented Feb 8, 2011 at 4:11

Hovercraft Full Of Eels · Accepted Answer · 2011-02-08 06:26:13Z

remove should work, and in fact it does work fine in a small example program that I created to help answer this question:

import java.util.Comparator;
import java.util.PriorityQueue;

public class TestPriorityQueue {
    public static void main(String[] args) {
        long[] noteTimes = {1103L, 0L, 500L, 0L, 220L, 1021212812012L};
        PriorityQueue<RecordedNote> noteQueue = new PriorityQueue<RecordedNote>(10,
                    new Comparator<RecordedNote>() {
                        @Override
                        public int compare(RecordedNote o1, RecordedNote o2) {
                            Long time1 = o1.getTime();
                            Long time2 = o2.getTime();

                            // uses Long's built in compareTo method, so we 
                            //don't have to worry as much about edge cases.
                            return time1.compareTo(time2); 
                        }
                    });
        for (int i = 0; i < noteTimes.length; i++) {
            RecordedNote note = new RecordedNote(noteTimes[i]);
            System.out.println(note);
            noteQueue.add(note);
        }
        System.out.println();
        while (noteQueue.size() > 0) {
            System.out.println(noteQueue.remove());
        }
    }
}

class RecordedNote {
    private long time;

    public RecordedNote(long time) {
        this.time = time;
    }

    public long getTime() {
        return time;
    }

    @Override
    public String toString() {
        return "[Time: " + time + "]";
    }
}

So this begs the question, why isn't it working for you? Myself, I don't see enough coherent code in your question to be able to answer this. We're not sure what is Song as I don't see this declared as a class or a variable, and I also don't see where you're using your PriorityQueue variable, recordedsong, anywhere. So I suggest you do the same thing as I: create a small compilable runnable program that we can run and modify and that demonstrates your problem, an http://sscce.org

Ria_546 · Accepted Answer · 2011-02-08 05:01:03Z

0

I guess there is a possibility for i getting 0. So modify compare method so that it returns a positive value rather than the result.

answered Feb 8, 2011 at 5:01

Ria_546

657 bronze badges

2 Comments

Hovercraft Full Of Eels Over a year ago

What's wrong with returning 0? What's wrong with returning -1?

user607545 Over a year ago

@Hovercraft Full Of Eels: I tried your code, and it seems to be working now. Thanks!

Thorn G · Accepted Answer · 2011-02-08 06:19:12Z

0

Reading the API docs for PriorityQueue, it states the following:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

My guess is that remove() is not obligated to follow the natural ordering, either.

answered Feb 8, 2011 at 6:19

Thorn G

12.8k2 gold badges48 silver badges56 bronze badges

2 Comments

Hovercraft Full Of Eels Over a year ago

I don't agree. remove has the same behavior of poll, and removes from the head of the queue except that remove throws an exception if the queue is empty. And when tested, remove works fine. Please see my answer post.

Thorn G Over a year ago

Evidence trumps gut every time -- upvoting your answer.

Collectives™ on Stack Overflow

Problem with Priority Queue

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related