Heap Concept Structure and Properties in DSA Java - Time & Space Complexity

Time Complexity: Heap Concept Structure and Properties

O(log n)

Understanding Time Complexity

We want to understand how the time to perform operations on a heap changes as the heap grows.

How does the structure of a heap affect the speed of its main actions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert element into a max heap
void insert(int[] heap, int value, int size) {
    heap[size] = value;
    int current = size;
    while (current > 0 && heap[current] > heap[(current - 1) / 2]) {
        int parent = (current - 1) / 2;
        int temp = heap[current];
        heap[current] = heap[parent];
        heap[parent] = temp;
        current = parent;
    }
}
    

This code inserts a new value into a max heap and restores the heap property by moving the new value up.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves the inserted element up the heap.
• How many times: It repeats as many times as the height of the heap, moving from leaf to root.

How Execution Grows With Input

As the heap size grows, the height grows slowly because the heap is a balanced tree.

Input Size (n)	Approx. Operations (loop iterations)
10	About 4
100	About 7
1000	About 10

Pattern observation: The number of steps grows slowly, roughly with the height of the heap, which increases logarithmically.

Final Time Complexity

Time Complexity: O(log n)

This means the time to insert grows slowly as the heap grows, because we only move up the tree height.

Common Mistake

[X] Wrong: "Insertion takes linear time because we might check every element in the heap."

[OK] Correct: We only move up the tree along one path, not through all elements, so the steps depend on the tree height, not total elements.

Interview Connect

Knowing heap operation times helps you explain efficient priority queues and sorting methods clearly and confidently.

Self-Check

"What if the heap was a linked tree instead of an array? How would the time complexity of insertion change?"

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