एक न्यूनतम-अधिकतम ढेर

Question

में हटाएं-अधिकतम ऑपरेशन मैं एक न्यूनतम-अधिकतम ढेर, एक प्रकार की डबल-एंडेड प्राथमिकता कतार लागू कर रहा हूं। न्यूनतम-अधिकतम ढेर के बारे में अधिक जानकारी के लिए आप यहां here देख सकते हैं।

सम्मिलन और हटाने-मिनट संचालन के लिए कोड सरल और नेट पर उपलब्ध हैं। लेकिन, मैं एक न्यूनतम अधिकतम ढेर पर हटाने-अधिकतम ऑपरेशन को लागू करने का भी प्रयास कर रहा हूं।

प्रारंभ में, मुझे लगा कि न्यूनतम-अधिकतम ढेर में डिलीट-मैक्स अधिकतम-न्यूनतम ढेर में डिलीट-मैक्स के समान होगा (यदि हम अधिकतम तत्व वाले न्यूनतम-अधिकतम ढेर के उप-भाग पर विचार करते हैं, तो यह अधिकतम- न्यूनतम ढेर)। तो, कार्यान्वयन मिनी-अधिकतम ढेर के मिनट को हटाने के लिए सरल और समान होगा।

लेकिन, वहाँ एक समस्या है:

के रूप में, ऊपर चित्र में देखा जा सकता है, हालांकि 70 में है अधिकतम तत्व, पिछले तत्व (12) न्यूनतम-अधिकतम ढेर के है नहीं subtree 70 युक्त। तो, क्या मैं इसे 70 के हटाने के बाद बाएं subtree में बाएं अंतर को बदलने के लिए उपयोग कर सकते हैं?

हम उस तत्व का उपयोग नहीं करते और बदले में अधिकतम-न्यूनतम ढेर की नष्ट-अधिकतम प्रक्रिया का पालन करें और 20 का उपयोग खाई को बदलने के लिए, अगले तत्व ढेर में डाला 10 और हमेशा के लिए की सही बच्चे पर किया जाएगा 9

कोई सही बच्चा नहीं होगा, तो क्या कोई मेरी मदद कर सकता है?

Answer 1

मेरा मानना ​​है कि अंतिम स्तर पर सही नोड को हटाने और इसे हटाए गए अधिकतम तत्व को बदलने के लिए इसका उपयोग करना सही है, भले ही यह पेड़ में पार हो जाए।

1. पिछले स्तर में सबसे दायीं ओर नोड निकाल रहा है अपरिवर्तनशीलताओं कि पेड़ के भीतर किसी भी नोड्स के लिए आयोजित करने की जरूरत है कि के किसी भी परिवर्तन नहीं करता है: तर्क निम्नलिखित है मिनट स्तरों पर नोड्स के सभी अभी भी तुलना में छोटे होते उनके सभी वंशज, और अधिकतम स्तर पर सभी नोड्स अभी भी उनके वंशजों से अधिक हैं।

2. पेड़ अभी भी एक पूर्ण बाइनरी पेड़ है।

बार जब आप इस नोड पर चले गए हैं, तो आप सामान्य Fixup प्रक्रिया एक अधिकतम मिनट ढेर में क्रम में उपयोग सुनिश्चित करना है कि बाईं सबट्री अपरिवर्तनशीलताओं अभी भी कर सकते हैं।

आशा है कि इससे मदद मिलती है!