Java. How does Random and remove work in Queue?

Question

Java

What, in fact,
happened ... Some kind of absurdity is happening.
I create a queue (PriorityQueue) and add values ​​\u200b\u200bto it.
1. I add random numbers ( Random )
2. I add a constant expression
and remove the first element in the queue ( remove (0)).
In the first case, the deletion takes place in 40-60 microseconds , in the second, in almost a millisecond , which is 500 times more
. Please, take a look at the code (or at least copy it to yourself).

private static final int COUNT = 1000000;

  public static void main(String[] args) {
    
    Random rand = new Random();
    
    Queue<Integer> arr = new PriorityQueue<Integer>();

    for (int i = 0; i < COUNT; i++)
      arr.add(rand.nextInt(100));               // заносим значения

    long before = System.nanoTime();			            // до
    arr.remove(0);	                              // удаляем первый элемент
    long total = System.nanoTime() - before;	    // после
    
    System.out.println("Microsecond: " + total / 1000);
  }

Click here!!! (photo)
Now, when adding, we change the random to constant numbers

// ...
        arr.add(100);
// ...

And here
Why is this happening?

Answer 1

PriorityQueue uses binary heap - this is a binary tree that is stored in a certain way in a linear array. The root of the tree is stored in the zero element, its children - in the next two (1st and 2nd), their children - in the next four.
After filling the PriorityQueue in the first variant with random numbers, the array will look like this.
Elements with a value of "0" with a probability of 99% will occur in the first 100 elements of the array.
If the PriorityQueue is filled with the same number, then the binary heap array will be like this
. Now let's look at the sources of the remove method

public boolean remove(Object o) {
       int i = indexOf(o);
       if (i == -1)
           return false;
        else {
            removeAt(i);
           return true;
       }
}

 private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

First, the index of the element in the array is searched. To do this, iterate over the array.
In the case of random elements, we will have to look at an average of 50 elements until we find an element with a value of "0", and when adding a constant, all 1,000,000.

Answer 2

Someone, test it yourself, maybe my Java is drizzling...

Answer 3

Your mistake is that the remove method doesn't actually take an index, but an object, i.e. you are not deleting the first element, but you are trying to delete the element in which the value 0 is written. Why the operations take such a different time, I think you can guess for yourself.