`add` and `addAll` from a `PriorityQueue` behave differently, why is this?

Question

When transferring elements from a PriorityQueue to an ArrayList I noticed List.add and List.addAll behave differently. But I'm not sure why.

Example code:

  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);
  }

The listAddAll contains [aaa, a, aa] while listAdd contains [aaa, aa, a]. I'd expect both to be the latter as that is the order specified by the comparator.

You are not observing the difference between `add` and `addAll` but between [traversing the queue](https://stackoverflow.com/q/2277430/2711488) and repeatedly calling `remove()` on it. — Holger, May 26 '20 at 14:52

score 2 · Accepted Answer · answered May 26 '20 at 07:37

Because the ArrayList.addAll is implemented to use Collection.toArray like this:

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;
}

And PriorityQueue.toArray is just a copy operation of the underlying array:

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

So, addAll will insert the queue elements according to their order in the queue field which is balanced binary heap that preserves the order of elements as a tree not a list. You're getting the raw array representing the tree not a sorted list.

`add` and `addAll` from a `PriorityQueue` behave differently, why is this?

1 Answers1