Question

What is the time complexity of building a heap from an unsorted array of size \(n\)?

• A. \(O(n \log n)\)
• B. \(O(n)\)
• C. \(O(\log n)\)
• D. \(O(n^2)\)

Hint:

A common misconception is that building a heap takes \(O(n \log n)\) because heapify is \(O(\log n)\). However, since most nodes are near the bottom of the tree and require minimal work, the total complexity becomes \(O(n)\).

Answer 1

The Correct Option is B

Concept: A binary heap can be constructed from an unsorted array using the bottom-up heap construction method (also known as Floyd’s Heap Construction Algorithm). Key ideas:

• The array representation of a heap allows efficient parent–child relationships.
• Starting from the last non-leaf node, we apply the {heapify} operation.
• Although heapify can take \(O(\log n)\) time for a single node, most nodes are near the bottom and require much less work.

The total work done across all nodes results in an overall complexity of \(O(n)\).
Step 1: Identify the last non-leaf node.}
For an array of size \(n\), all elements from index \( \lfloor n/2 \rfloor + 1 \) to \(n\) are leaves. So heap construction begins from node \( \lfloor n/2 \rfloor \) and moves upward to the root. \[ i = \left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{n}{2} \right\rfloor - 1, \ldots, 1 \]
Step 2: Apply heapify to each node.}
Each node is heapified to maintain the heap property (max-heap or min-heap). Heapify takes at most \(O(h)\) time, where \(h\) is the height of the node. Nodes closer to the leaves have smaller heights and therefore require less work.
Step 3: Compute the total complexity.}
The total cost is the sum of heapify costs at each level of the tree: \[ T(n) = \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) \] Evaluating this summation gives: \[ T(n) = O(n) \] Thus, building a heap from an unsorted array runs in linear time.