CODEWITHSUNDEEP
javaqueuecomparatorpriority-queuecomparable
Mohan Kumar
Mohan Kumar

Reputation: 3

sort the elements in java using priority queue

I want to sort the elements using Priority Queue in Java.

Here is my code. What is wrong in it?

import java.io.*;
import java.util.*;

class PQ {
    static class IntCompare implements Comparator<Integer>{
        @Override
        public int compare(Integer arg0, Integer arg1) {
            if(arg0 > arg1)
                return -1;
            else if(arg0 < arg1)
                return 1;
            else
                return 0;
        }
   }

    public static void main (String[] args) {
        int a[] = { 1, 3, 8, 5, 2, 6 };

        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);

        for(int i = 0; i < a.length; i++)
            pq.add(a[i]);

        System.out.println(pq);
    }
}

my output is:

8, 5, 6, 1, 2, 3

correct output:

8, 6, 5, 3, 2, 1

Upvotes: 0

Views: 301

Answers (3)

xingbin
xingbin

Reputation: 28289

When you call System.out.println(pq), the toString method is called implicitly.

The toString method of PriorityQueue extends from AbstractCollection, which

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]").

While the iterator of PriorityQueue is not guaranteed to traverse in particular order:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

since the queue is based on heap.

You can poll elements one by one to get ordered elements:

while (pq.size() != 0) {
    System.out.print(pq.poll() + ","); // 8,6,5,3,2,1,
}

Upvotes: 1

amrender singh
amrender singh

Reputation: 8239

Try the following, list contains items in sorted order. The priority key by itself not maintain the elements in sorted order, it just keeps the top element as minimum or maximum based on your implementation of the PQ.

public static void main (String[] args) {
        int a[]={1,3,8,5,2,6};
        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);
        for(int i=0;i<a.length;i++)
            pq.add(a[i]);
        ArrayList<Integer> list  = new ArrayList<>();
        while(!pq.isEmpty()){
            list.add(pq.poll());
        }
        for(Integer i : list)
            System.out.println(i);
}

Upvotes: 0

AndrejH
AndrejH

Reputation: 2119

You should poll() all the elements until the queue is empty and save them somewhere to get them ordered.

Upvotes: 0

Related Questions