हीपबनाने की समय जटिलता

इनपुट एरे के हीप के निर्माण के लिए निम्नलिखित एल्गोरिथ्म पर विचार करें। निर्माण (ए) हीप: = आकार (ए); मैं के लिए: = मंजिल (ढेर / 2) 1 तक जोर से करो (ए, आई); के लिए अंत समाप्त उपरोक्त एल्गोरिथ्म पर एक त्वरित नज़र बताती है कि रनिंग टाइम O (n lg (n)) है, क्योंकि प्रत्येक कॉल हाइपिफाई की लागत O (lg (n)) और बिल्ड-हीप O (n) ऐसी कॉल करता है। यह ऊपरी बाध्य, हालांकि सही है, स्पर्शोन्मुख रूप से तंग नहीं है। हम यह देखते हुए बाध्य कर सकते हैं कि हाइपिफाई का रनिंग टाइम पेड़ की ऊँचाई 'h' (जो lg (n) के बराबर है, जहाँ n नोड्स की संख्या है) और अधिकांश उप-पेड़ों की ऊँचाई पर निर्भर करता है। छोटे। जैसे ही हम पेड़ के साथ ऊपर की ओर बढ़ते हैं, ऊँचाई 'h' बढ़ जाती है। बिल्ड-हीप की लाइन -3, ऊंचाई = 1 के साथ अंतिम आंतरिक नोड (ढेर / 2) के सूचकांक से एक लूप चलाती है, जड़ के सूचकांक (1) के साथ ऊंचाई = lg (n)। इसलिए, हाइपिफाई प्रत्येक नोड के लिए अलग-अलग समय लेता है, जो O (h) है। एक ढेर के निर्माण की समय जटिलता को खोजने के लिए, हमें पता होना चाहिए कि ऊँचाई वाले नोड्स की संख्या कितनी है।