Question:
Consider an array of size \(n\) representing a Binary Max-Heap. What is the time complexity to build this Max-Heap using bottom-up
BuildHeap?
\(n\) आकार के एक ऐरे पर विचार करें जो बाइनरी मैक्स-हीप का प्रतिनिधित्व करता है। बॉटम-अप
BuildHeap दृष्टिकोण का उपयोग करके इस मैक्स-हीप के निर्माण की समय जटिलता क्या है?
Options:
- \(O(n)\)
- \(O(n \log n)\)
- \(O(\log n)\)
- \(O(n^2)\)
- \(O(n)\)
- \(O(n \log n)\)
- \(O(\log n)\)
- \(O(n^2)\)
Correct Answer: a)
Explanation:
Building a heap from an arbitrary array of \(n\) elements using the bottom-up approach (calling
heapify from index \(n/2\) down to 1) runs in linear time \(O(n)\). This is because the number of nodes at height \(h\) is at most \(\lceil n/2^{h+1} \rceil\), and the total cost \(\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} O(h) = O(n)\).
बॉटम-अप
BuildHeap कलनविधि की समय जटिलता \(O(n)\) (रैखिक समय) होती है, क्योंकि अधिकांश नोड पत्तों (leaves) के पास स्थित होते हैं जिनकी ऊंचाई बहुत कम होती है।