Search code examples
javacollectionspriority-queue

Java PriorityQueue Seems to Change Previously Added Values on Calling add()


I am left puzzled as the priority queue I am working with seems to change or reorder the previously added values in a loop while adding new values. It only happens with this test case so far.

Here are some snips of my debugger:

Before adding 6th element:

enter image description here

After adding 6th element:

enter image description here

The code example is as follows:

package mixedobjectsset;

import java.util.PriorityQueue;
import java.util.Queue;

public class MixedObjectsSet {

private static final char union = '\u222A';
private static final char intersection = '\u2229';
private static final char product = '\u2A2F';
private static final char difference = '\u2216';


public static void main(String[] args) {
    MixedObjectsSet m = new MixedObjectsSet();
    m.operatorsQueue("(({1,2}" + difference + "{1,3})" +
            difference + "({1 } " + union + "{4})) " + union + "{1,3}");
}

public Queue operatorsQueue(String expr){

    Queue<Character> queue = new PriorityQueue<>();
    char[] exprCharArr = expr.toCharArray();

    for (int j = 0; j < exprCharArr.length; j++) {
        switch (exprCharArr[j]){
            case '(':
                queue.add('(');
                break;
            case ')':
                queue.add(')');
                break;
            case '\u222A':
                queue.add(union);
                break;
            case '\u2216':
                queue.add(difference);
                break;
            case '\u2A2F':
                queue.add(product);
                break;
            case '\u2229':
                queue.add(intersection);
                break;
            case ';':
                queue.add(';'); //for adding to storage instead of calculations
                break;
        }
    }


    System.out.println("queue.toString() = " + queue.toString());

    return queue;


   }
}

Solution

  • Array queue in PriorityQueue implementation does NOT store elements in the order they will be polled out of the queue. PriorityQueue is a binary heap, and the heap is stored in queue array as described here. It means that you should not look in the queue array (unless you know how binary heap exactly works), because it's an encapsulated implementation detail that does a different thing that you may expect from its name.