Для работы PriorityQueue используется binary heap - это двоичное дерево, которое хранится определенном образом в линейном массиве. Корень дерева храниться в нулевом элементе, его дети - в следующих двух (1ом и 2ом), их дети - в следующих четырех.
После заполнения PriorityQueue в первом варианте, случайными числами, массив будет выглядить так
Элементы со значением "0" с вероятностью 99% будут встречаться в первых 100 элементах массива.
Если заполнить PriorityQueue одним и тем же числом - то массив двоичной кучи будет таким
Теперь посмотрим исходники метода
remove 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;
}
Сначала ищется индекс элемента в массиве. Для этого используется проход по массиву.
В случае со случайными элементами придется просматривать в среднем 50 элементов пока не найдем элемента со значением "0", а при добавлении константы - все 1 000 000.
