`add` и` addAll` из PriorityQueue ведут себя по-разному, почему это так?

Question

При передаче элементов из PriorityQueue в ArrayList я заметил, что List.add и List.addAll ведут себя по-разному. Но я не уверен, почему.

Пример кода:

  public static void main(String[] args) {
    PriorityQueue<String> heap = new PriorityQueue<>(Comparator.reverseOrder());
    heap.add("a");
    heap.add("aa");
    heap.add("aaa");

    ArrayList<String> listAddAll = new ArrayList<>();
    listAddAll.addAll(heap);
    System.out.println(listAddAll);

    ArrayList<String> listAdd = new ArrayList<>();
    while (!heap.isEmpty()){
      listAdd.add(heap.remove());
    }
    System.out.println(listAdd);
  }

listAddAll содержит [aaa, a, aa], а listAdd содержит [aaa, aa, a]. Я ожидал, что оба будут последними, так как это порядок, указанный компаратором.

Answer 1

Поскольку ArrayList.addAll реализован для использования Collection.toArray следующим образом:

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

А PriorityQueue.toArray - это просто операция копирования базового массива:

public Object[] toArray() {
        return Arrays.copyOf(queue, size);
}

Таким образом, addAll вставит элементы очереди в соответствии с их порядком в поле queue, которое представляет собой сбалансированную двоичную кучу, которая сохраняет порядок элементов в виде дерева, а не списка. Вы получаете необработанный массив, представляющий дерево, а не отсортированный список.