Min-heap and max-heap properties in Data Structures Theory - Time & Space Complexity

Time Complexity: Min-heap and max-heap properties

O(log n)

Understanding Time Complexity

We want to understand how the time to maintain heap properties changes as the heap grows.

Specifically, how operations like insertion or removal scale with the number of elements.

Scenario Under Consideration

Analyze the time complexity of restoring heap properties after insertion.

function heapifyUp(heap, index) {
  while (index > 0) {
    let parent = Math.floor((index - 1) / 2);
    if (heap[parent] <= heap[index]) break; // For min-heap
    swap(heap, parent, index);
    index = parent;
  }
}
    

This code moves a newly added element up the heap to keep the min-heap property intact.

Identify Repeating Operations

Look at the loop that moves the element up the tree.

• Primary operation: Comparing and swapping with the parent node.
• How many times: At most once per level of the heap, moving from leaf to root.

How Execution Grows With Input

Each time we add an element, it may move up through the heap levels.

Input Size (n)	Approx. Operations
10	About 4 comparisons/swaps
100	About 7 comparisons/swaps
1000	About 10 comparisons/swaps

Pattern observation: Operations grow slowly, roughly proportional to the height of the heap, which increases with the logarithm of n.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap grows slowly as the heap gets bigger, only increasing with the height of the tree.

Common Mistake

[X] Wrong: "Fixing the heap after insertion takes time proportional to the number of elements (O(n))."

[OK] Correct: The heap is a balanced tree, so the element only moves up the height of the tree, which is much smaller than the total number of elements.

Interview Connect

Understanding heap operations and their time complexity helps you explain efficient priority queue implementations and is a common topic in coding interviews.

Self-Check

"What if the heap was a max-heap instead of a min-heap? How would the time complexity of restoring the heap property change?"