Isso é direto doDocs Java:

Esta classe e seu iterador implementam todos os métodos opcionais das interfaces Collection e Iterator.O Iterator fornecido no método iterator () não tem garantia de atravessar os elementos da fila de prioridade em qualquer ordem específica. Se você precisar de uma travessia ordenada, considere usar Arrays.sort (pq.toArray ()).

Então, basicamente, meu PriorityQueue funciona bem, mas imprimi-lo na tela usando seu próprio método toString () embutido me levou a ver essa anomalia em ação, e fiquei imaginando se alguém poderia explicar por que o iterador forneceu (e usou internamente) não atravessa o PriorityQueue em sua ordem natural?