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