How Java PriorityQueue sorting elements

Question

I am writing a simple program using priority queue in which I am adding elements to it, I am not getting how it is sorting the elements internally(java doc says it's based on natural sorting order but how ?).

Java code :

PriorityQueue pQueue = new PriorityQueue();

    // Adding items to the pQueue using add()
    pQueue.add(10);
    pQueue.add(20);
    pQueue.add(15);
    pQueue.add(50);
    pQueue.add(3);
    pQueue.add(2);

Output is: [2, 10, 3, 50, 20, 15]

score 1 · Accepted Answer · answered Apr 11 '21 at 09:19

You got it right but partially as you have missed the first part of it.

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

AS you can see it's clearly mentioned that it is based on priority heap. Now if you would like to understand what is Heap you can refer Binary Heap or in one line if you wanna understand basically there are 3 types of Heap -> Min & Map. Java's priority queue is using Min Heap, in this case

the key at root must be minimum among all keys present in Binary Heap and the same property must be recursively true for all nodes in the same tree

To implement this java use bit shifting also:

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable key;
    int parent;
    for(key = (Comparable)x; k > 0; k = parent) {
        parent = k - 1 >>> 1;
        Object e = es[parent];
        if (key.compareTo(e) >= 0) {
            break;
        }

        es[k] = e;
    }

    es[k] = key;
}

How Java PriorityQueue sorting elements

1 Answers1