Understanding Binary Heap with PriorityQueue

Java's PriorityQueue is commonly implemented with a binary heap. That means the queue keeps enough order to find and remove the highest-priority item efficiently, but it does not keep the whole collection sorted at every moment.

The example input

Suppose we add these words in order:

one two three four five six seven

For Java String values, the default priority is lexicographic order. With this set of words, the sorted removal order is:

five, four, one, seven, six, three, two

That order surprises students because dictionary-style comparison is character by character: "five" comes before "four" because i comes before o after the first letter f.

Correct Java example

PriorityQueue<String> words = new PriorityQueue<>();

for (String word : "one two three four five six seven".split(" "))
{
    words.add(word);
}

System.out.println("peek: " + words.peek());
System.out.println("printed queue: " + words);

while (!words.isEmpty())
{
    System.out.print(words.poll() + " ");
}

Correct output

peek: five
printed queue: [five, four, seven, two, one, three, six]
five four one seven six three two

The important part is not that every Java program should depend on the exact printed queue order. The important part is that peek() and poll() follow priority order. The order shown by toString() reflects the internal heap array used by the implementation and is not a fully sorted list.

What the heap property actually guarantees

A min-heap only guarantees that each parent is less than or equal to its children. It does not guarantee that siblings are sorted, and it does not guarantee that a level reads left-to-right in sorted order.

One valid internal heap array after the insertions is:

[five, four, seven, two, one, three, six]

Interpreted as a heap tree, that array means:

          five
       /        \
    four        seven
   /   \       /    \
 two   one   three   six

This is valid because each parent is lexicographically before its children:

• five < four and five < seven
• four < two and four < one
• seven < three and seven < six

Notice what is not required: one does not need to appear near the root just because it comes third in sorted order. It only needs to be below a parent that is smaller than it.

Why polling becomes sorted

When poll() removes five, the heap repairs itself so the next smallest word becomes the root. Repeating poll() gives sorted priority order because each removal asks the heap to expose the next minimum.

Operation	Result	Why
peek()	five	Smallest item is at the root.
toString()	[five, four, seven, two, one, three, six]	Shows heap storage, not sorted order.
Repeated poll()	five four one seven six three two	Each removal repairs the heap and exposes the next minimum.

Student takeaway

For tracing questions, separate these three ideas: peek() gives the current minimum, poll() repeatedly gives sorted priority order, and printing the queue does not prove the whole structure is sorted.