Heap Concept Structure and Properties in DSA Java

Mental Model

A heap is a special tree where each parent is bigger (max heap) or smaller (min heap) than its children, making it easy to find the biggest or smallest item quickly.

Analogy: Imagine a pyramid of boxes where each box is heavier than the boxes below it, so the heaviest box is always on top and easy to grab.

       [50]
      /     \
   [30]     [20]
   /  \     /  \
 [10] [15] [5] [7]

Dry Run Walkthrough

Input: Build a max heap from array: [10, 20, 15, 30, 50]

Goal: Create a max heap where the largest number is at the root and each parent is larger than its children

Step 1: Start with array as a binary tree: 10 at root, 20 and 15 as children, 30 and 50 as next level

       [10]
      /     \
   [20]     [15]
   /  \
 [30] [50]

Why: We need to organize this tree to satisfy max heap property

Step 2: Compare 30 with its parent 20, swap because 30 > 20

       [10]
      /     \
   [30]     [15]
   /  \
 [20] [50]

Why: Parents must be bigger than children, so swap to fix violation

Step 3: Compare 50 with its parent 30, swap because 50 > 30

       [10]
      /     \
   [50]     [15]
   /  \
 [20] [30]

Why: Continue fixing heap property upwards

Step 4: Compare 50 with root 10, swap because 50 > 10

       [50]
      /     \
   [10]     [15]
   /  \
 [20] [30]

Why: Root must be largest in max heap

Step 5: Compare 20 with its parent 10, swap because 20 > 10

       [50]
      /     \
   [20]     [15]
   /  \
 [10] [30]

Why: Fix heap property on left subtree

Step 6: Compare 30 with its parent 15, swap because 30 > 15

       [50]
      /     \
   [20]     [30]
   /  \
 [10] [15]

Why: Fix heap property on right subtree

Result:

       [50]
      /     \
   [20]     [30]
   /  \
 [10] [15]

Annotated Code

DSA Java

public class MaxHeap {
    private int[] heap;
    private int size;

    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    private int parent(int index) { return (index - 1) / 2; }
    private int leftChild(int index) { return 2 * index + 1; }
    private int rightChild(int index) { return 2 * index + 2; }

    public void insert(int value) {
        heap[size] = value;
        int current = size;
        size++;

        // Bubble up to maintain max heap property
        while (current > 0 && heap[current] > heap[parent(current)]) {
            int temp = heap[current];
            heap[current] = heap[parent(current)];
            heap[parent(current)] = temp;
            current = parent(current);
        }
    }

    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        int[] input = {10, 20, 15, 30, 50};
        for (int val : input) {
            maxHeap.insert(val);
        }
        maxHeap.printHeap();
    }
}

while (current > 0 && heap[current] > heap[parent(current)]) {

bubble up current node while it is greater than its parent to maintain max heap property

int temp = heap[current]; heap[current] = heap[parent(current)]; heap[parent(current)] = temp;

swap current node with parent to fix heap order

current = parent(current);

move current pointer up to parent to continue checking

Output

50 20 30 10 15 

Complexity Analysis

Time: O(n log n) because each insert can bubble up up to the root in O(log n) and we do n inserts

Space: O(n) because we store all elements in an array representing the heap

vs Alternative: Building heap by repeated insertions is O(n log n), but heapify method can build heap in O(n) time

Edge Cases

empty heap

no elements to insert or print, output is empty

DSA Java

for (int val : input) { maxHeap.insert(val); }

single element

heap contains only one element, no bubbling needed

DSA Java

while (current > 0 && heap[current] > heap[parent(current)])

all elements equal

no swaps happen because no element is greater than parent

DSA Java

while (current > 0 && heap[current] > heap[parent(current)])

When to Use This Pattern

When you need quick access to the largest or smallest element and want to insert or remove elements efficiently, use a heap because it keeps the biggest or smallest item at the top.

Common Mistakes

Mistake: Not bubbling up after insertion, leaving heap property broken
Fix: Add a loop to swap the inserted element with its parent while it is greater (max heap) or smaller (min heap)

Mistake: Using incorrect parent or child index calculations
Fix: Use parent = (index-1)/2, left child = 2*index+1, right child = 2*index+2 formulas

Summary

A heap is a tree-based structure where parents are always bigger (max heap) or smaller (min heap) than their children.

Use a heap when you want fast access to the largest or smallest element and efficient insertions.

The key is to keep the heap property by bubbling inserted elements up to their correct position.

Practice

1. What is a key property of a max-heap data structure?

easy

A. The tree is always a complete binary tree but not necessarily balanced

B. The value of each parent node is less than or equal to its children

C. All leaf nodes have the same value

D. The value of each parent node is greater than or equal to its children

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that every parent node's value is greater than or equal to its children.

2. Step 2: Compare options with max-heap definition

   The value of each parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or unrelated properties.

3. Final Answer:

   The value of each parent node is greater than or equal to its children -> Option D

4. Quick Check:

   Max-heap parent ≥ children = A [OK]

Hint: Max-heap means parent node ≥ children nodes [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaf nodes must have same value
• Ignoring the complete binary tree requirement

2. Which of the following is the correct way to declare a min-heap using Java's PriorityQueue?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.reverseOrder());

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.naturalOrder());

Solution

1. Step 1: Recall Java PriorityQueue default behavior

   By default, PriorityQueue in Java is a min-heap, so no comparator is needed.

2. Step 2: Analyze options for min-heap declaration

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); uses default constructor, which creates a min-heap. A and B use reverseOrder creating max-heap, C uses non-existent Collections.naturalOrder().

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); -> Option C

4. Quick Check:

   Default PriorityQueue = min-heap = D [OK]

Hint: Default PriorityQueue in Java is min-heap [OK]

Common Mistakes:

• Using reverseOrder() creates max-heap, not min-heap
• Confusing naturalOrder() with reverseOrder()
• Adding unnecessary comparator for default min-heap

3. What will be the output of the following Java code snippet?

import java.util.PriorityQueue;
public class TestHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.add(30);
    heap.add(10);
    heap.add(20);
    System.out.print(heap.poll() + ", " + heap.poll() + ", " + heap.poll());
  }
}

medium

A. 20, 10, 30

B. 10, 20, 30

C. 30, 20, 10

D. 10, 30, 20

Solution

1. Step 1: Understand PriorityQueue behavior

   Java's PriorityQueue is a min-heap by default, so poll() returns the smallest element.

2. Step 2: Trace poll() calls

   Elements added: 30, 10, 20. First poll() returns 10, second 20, third 30.

3. Final Answer:

   10, 20, 30 -> Option B

4. Quick Check:

   poll() returns min element each time = 10,20,30 [OK]

Hint: poll() returns smallest element in min-heap [OK]

Common Mistakes:

• Assuming poll() returns elements in insertion order
• Confusing min-heap with max-heap behavior
• Not realizing poll() removes elements

4. Identify the error in the following code that attempts to create a max-heap using Java's PriorityQueue:

import java.util.PriorityQueue;
import java.util.Collections;
public class MaxHeapExample {
  public static void main(String[] args) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
    maxHeap.add(5);
    maxHeap.add(15);
    maxHeap.add(10);
    System.out.println(maxHeap.poll());
  }
}

medium

A. PriorityQueue is not initialized with a comparator for max-heap

B. PriorityQueue cannot store Integer objects

C. poll() method does not exist for PriorityQueue

D. add() method cannot be used to insert elements

Solution

1. Step 1: Check PriorityQueue initialization

   The code initializes PriorityQueue without a comparator, so it defaults to min-heap.

2. Step 2: Identify max-heap creation mistake

   To create max-heap, PriorityQueue must be initialized with Collections.reverseOrder() comparator.

3. Final Answer:

   PriorityQueue is not initialized with a comparator for max-heap -> Option A

4. Quick Check:

   Missing comparator = B [OK]

Hint: Max-heap needs reverseOrder() comparator in PriorityQueue [OK]

Common Mistakes:

• Assuming default PriorityQueue is max-heap
• Thinking poll() method is invalid
• Believing add() cannot insert elements

5. Given a max-heap represented as an array: [50, 30, 40, 10, 20], which of the following arrays represents the heap after inserting the element 35 and re-heapifying?

hard

A. [50, 30, 40, 10, 20, 35]

B. [50, 35, 40, 10, 20, 30]

C. [50, 40, 30, 10, 20, 35]

D. [50, 40, 35, 10, 20, 30]

Solution

1. Step 1: Insert 35 at the end of the array

   Array becomes [50, 30, 40, 10, 20, 35].

2. Step 2: Re-heapify by comparing 35 with its parent

   Parent of index 5 is index 2 (40). Since 35 <= 40, no swap needed. Heap property is maintained.

3. Step 3: Check if bubbling up is needed

   Since 35 < 40, no bubble up occurs, so the array remains [50, 30, 40, 10, 20, 35]. However, this matches [50, 30, 40, 10, 20, 35], but [50, 30, 40, 10, 20, 35] is not the correct max-heap after insertion because 35 should bubble up if possible.

4. Step 4: Correct bubbling up

   Actually, 35 is less than 40, so no swap with parent. The heap remains [50, 30, 40, 10, 20, 35].

5. Final Answer:

   [50, 30, 40, 10, 20, 35] -> Option A

6. Quick Check:

   Insert 35 at end, parent(5)=40 >= 35, no bubble up = D [OK]

Hint: Insert at end, then bubble up to fix max-heap [OK]

Common Mistakes:

• Not bubbling up after insertion
• Swapping with wrong parent index
• Assuming insertion at root