Вставка в двоичную кучу происходит быстрее по мере увеличения размера кучи? ⇐ JAVA

[Anonymous]

offer() в PriorityQueue, похоже, выполняется быстрее по мере увеличения размера очереди.
Результаты теста
Я реализовал минимальную кучу в Java и хотел проверьте временную сложность вставки в него. Результаты были очень странными, так как казалось, что вставка происходит быстрее, чем больше куча, хотя количество свопов (плаваний) больше.
Я подумал, что в моем файле может быть ошибка. реализации, поэтому я попробовал PriorityQueue в JCF, и, к моему удивлению, результаты оказались такими же!
Вот тест, который я написал для расчета времени.
public static void main(String[] args) {
PriorityQueue p = new PriorityQueue(200000000); //capacity: 200 Million

int n = 100000000;
for(int i = 0; i < n; i++){
p.offer(100 + Math.random() * 10000);
}

int numOfInsertions = 5;
long start = System.nanoTime();

p.offer(Math.random() * 100); //inserted elements are less than all elements
p.offer(Math.random() * 100);//in the heap, to ensure a full swim all the way up
p.offer(Math.random() * 100);//to the root
p.offer(Math.random() * 100);
p.offer(Math.random() * 100);

long end = System.nanoTime();

System.out.println((end - start)/numOfInsertions);

System.out.println(p.peek()); //ensure that the elements less than 100
//were inserted
}


Подробнее здесь: https://stackoverflow.com/questions/791 ... ets-larger