Understanding Binary Heap with PriorityQueue

By /

Introduction

A binary heap is a specialized tree-based data structure that efficiently maintains a priority queue. In Java, PriorityQueue implements a min-heap by default, ensuring that the smallest element is always at the root while keeping the heap balanced.

In this article, we will explore how a binary heap is constructed step by step using the example input:

"one two three four five six seven"

By visualizing each insertion step, you’ll gain a clear understanding of how Java’s PriorityQueue dynamically maintains heap order.

What is a Min-Heap?

A min-heap is a complete binary tree where:

  1. The smallest element is always at the root (peek()).
  2. Each parent node is smaller than its children.
  3. The tree maintains balance by filling levels from left to right.

Example of a valid min-heap:

             five
       four   seven
    two   one   three   six

This structure ensures fast insertion and deletion operations, making priority queues useful for scheduling, shortest path algorithms, and more.

Building a Binary Heap Step-by-Step

Let’s construct the heap step by step by inserting words from our input string into a PriorityQueue.

Using Java’s PriorityQueue (Min-Heap), which maintains lexicographical order, let’s insert elements one by one while ensuring:

  1. Elements are inserted in level order (left to right).
  2. Heapify-up occurs when necessary to maintain the heap property.
  3. The root is always the smallest lexicographically.

Input Words:

"one two three four five six seven"

Lexicographical order (dictionary order):

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

Step-by-Step Heap Insertions

Step 1: Insert "one"

    one

✅ "one" is the first element, so it becomes the root.

Step 2: Insert "two"

       one
    two

✅ "two" is inserted as the left child.

Step 3: Insert "three"

         one
    two   three

✅ "three" is inserted as the right child.

Step 4: Insert "four"

  1. Insert "four" in the next available position (left to right).
  2. Heapify-up: Compare "four" with its parent ("two").
  3. "four" is smaller than "two", so swap occurs.
           one
    four   three
  two

✅ "four" moves up and swaps with "two".

Step 5: Insert "five"

  1. Insert "five" at the next available position.
  2. Compare "five" with its parent ("four").
  3. "five" is smaller than "four", so swap occurs.
           one
    five        three
  two   four

✅ "five" moves up and becomes the left child of "one".

Step 6: Insert "six"

  1. Insert "six" at the next available position.
  2. Compare "six" with its parent ("three").
  3. "six" is greater than "three", so no swap needed.
          one
    five          three
  two   four   six

✅ "six" remains as the child of "three".

Step 7: Insert "seven"

  1. Insert "seven" at the next available position.
  2. Compare "seven" with its parent ("three").
  3. "seven" is greater than "three", so no swap needed.
            one
    five          three
  two   four   six   seven

✅ "seven" is correctly placed.

Final Heap Structure Before Any Removals

             five
     four         seven
  two   one   three   six

Final Heap Order in PriorityQueue

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

Why Does This Order Appear?

  • PriorityQueue internally maintains a min-heap, but toString() does NOT show a fully sorted list.
  • Only the root ("five") is guaranteed to be the smallest element.
  • Other elements are arranged to maintain heap order efficiently.

Final Summary

✅ Correct heap structure is achieved.
✅ Heap properties are followed with swaps only when necessary.
✅ Output order ([five, four, seven, two, one, three, six]) matches expectations.

Would you like an interactive

Understanding Heap Properties in Java’s PriorityQueue

  1. Insertion (offer() / add())
    • New elements are added at the next available position.
    • The heap restructures itself (heapify-up) if necessary to maintain order.
  2. Retrieval (peek())
    • The smallest element (highest priority) is always available at the root.
  3. Deletion (poll())
    • The root element is removed.
    • The last element replaces it, and heapify-down ensures correct heap order.

Why Does PriorityQueue.toString() Not Show a Sorted List?

When we print the priority queue using toString(), it does not display a fully sorted order because:

  • The internal heap structure is not a fully sorted list.
  • Only the smallest element is guaranteed to be at the root.
  • The rest of the elements are stored in heap order, which prioritizes quick access over sequential sorting.

However, removing elements (poll()) one by one results in a fully sorted sequence.

Scroll to Top