Почему java.util.concurrent.PriorityBlockingQueue использует массив, а не связанный список

Question

На мой взгляд, самое большое преимущество массива в том, что мы можем получить доступ к любому элементу с помощью O (1). Но очередь может быть доступна только из головы или хвоста.

Кроме того, PriorityBlockingQueue является отсортированной коллекцией, что означает, что каждая операция добавления будет вызывать смещение всех более крупных (или более мелких) элементов. Это довольно дорого.

Так что я не понимаю, почему вместо этого не использовать связанный список.

Answer 1

Кроме того, PriorityBlockingQueue - это отсортированная коллекция, что означает, что каждая операция добавления будет вызывать смещение всех более крупных (или меньших) элементов.

Вы неправильно поняли внутреннюю работу PriorityBlockingQueue: он не сдвигается вверх или вниз по всему массиву;это действительно было бы слишком дорого.Вместо этого он использует структуру данных с именем heap , которая использует массив для хранения, но не применяет к нему «простую» индексацию.Вместо этого он сохраняет элементы в древовидной форме, делая возможным вставку и удаление O (log ₂ n).

Подробнее о том, как PriorityBlockingQueue поддерживает кучу, см. реализации из shiftDown и shiftUp в PriorityQueue.java.

Answer 2

Поскольку базовая структура данных на самом деле представляет собой двоичную кучу, которая наиболее эффективно реализуется через массив и которая в свою очередь обеспечивает производительность O (log (N)) при добавлении и удалении.LinkedList не может быть столь же эффективным, как куча.

Кроме того, PriorityBlockingQueue является отсортированной коллекцией, что означает, что каждая операция добавления приведет к смещению всех более крупных (или более мелких) элементов.

Нет, не будет.Это приведет к операции повторной кучи, которая значительно эффективнее, чем вы описываете.