एक अधिकतम ढेर पेड़ बनाने के लिए, हम या तो siftDown या siftUp कर सकते हैं, हम रूट से शुरू करते हैं और इसे अपने दो बच्चों से तुलना करते हैं, फिर हम दोनों बच्चों के बड़े तत्व के साथ प्रतिस्थापित करते हैं, अगर दोनों बच्चे छोटे होते हैं तो हम रुकते हैं, अन्यथा हम तब तक उस तत्व को तब तक छोड़ते रहते हैं जब तक हम एक पत्ता नोड तक पहुंच जाते हैं (या फिर, जब तक कि उसके तत्व दोनों बड़े नहीं होते हैं)।siftDown siftUp से बेहतर क्यों है?
अब हम केवल, कि n/2 बार करने की आवश्यकता होगी क्योंकि पत्तियों की संख्या n/2 है, और पत्ते ढेर संपत्ति जब पिछली बार हमने पहले स्तर पर पिछले तत्व heapifying समाप्त संतुष्ट करेगा (पत्तियों से पहले) - तो हम n/2 तत्वों को ढेर करने के लिए छोड़ देंगे।
अब अगर हम siftUp का उपयोग करते हैं, तो हम पत्तियों से शुरू करेंगे, और अंततः हमें सभी n तत्वों को तेज़ करने की आवश्यकता होगी।
मेरा प्रश्न है: जब हम siftDown का उपयोग करते हैं, तो हम मूल रूप से siftUp का उपयोग करते समय केवल एक तुलना की तुलना में दो तुलना (मूल रूप से अपने बच्चों को तुलना करना) नहीं कर रहे हैं, क्योंकि हम केवल उस तत्व की तुलना अपने माता-पिता से करते हैं ? यदि हां, तो इसका मतलब यह नहीं होगा कि हम जटिलता को दोगुना कर रहे हैं और वास्तव में एक ही सटीक जटिलता के साथ समाप्त हो रहे हैं? जबकि siftUp के बार-बार कॉल के साथ यह निर्माण O(nlogn) की एक जटिलता है
मुझे लगता है कि इस प्रश्न का उत्तर लागू होता है। शायद एक डुप्लिकेट। https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity –