एक सममित न्यूनतम-अधिकतम ढेर (SMMH) को एक पूर्ण बाइनरी ट्री के रूप में परिभाषित किया गया है जिसमें रूट को छोड़कर प्रत्येक नोड में ठीक एक तत्व होता है। SMMH का रूट खाली होना चाहिए और SMMH में नोड्स की कुल संख्या m + 1 है, जहाँ m तत्वों की संख्या है।
मान लीजिए y SMMH का कोई नोड है। मान लें कि तत्व (y) y पर निहित उप-वृक्ष में तत्व हैं, लेकिन y में तत्व (यदि कोई हो) को छोड़कर। मान लें कि तत्व (y) j=. y निम्नलिखित गुणों को पूरा करता है:
- y के बाएं बच्चे में तत्वों (y) में न्यूनतम तत्व है।
- y के दाहिने बच्चे (यदि कोई हो) में तत्वों (y) में अधिकतम तत्व है।
चित्र 1 एक उदाहरण SMMH दिखाता है जिसमें 12 तत्व हैं।
जब y 81 के साथ नोड को दर्शाता है, तत्व (y) ={7, 15, 31, 41}; y के बाएं बच्चे में तत्वों (y) में न्यूनतम तत्व 6 है; और y के दाहिने बच्चे में तत्वों (y) में अधिकतम तत्व 41 है। हम सत्यापित कर सकते हैं कि इस SMMH का प्रत्येक नोड y बताए गए गुणों को पूरा करता है।
चूंकि एक SMMH को एक पूर्ण बाइनरी ट्री के रूप में निरूपित किया जाता है, इसे एक अंतर्निहित डेटा संरचना के रूप में संग्रहीत किया जाता है जो एक पूर्ण बाइनरी ट्री के मानक मैपिंग को एक सरणी में लागू करता है। जब m =1, न्यूनतम और अधिकतम तत्व समान होते हैं और SMMH के रूट के बाएँ बच्चे में समाहित होते हैं।
जब m> 1, न्यूनतम तत्व रूट के बाएं बच्चे में होता है और अधिकतम रूट के दाहिने बच्चे में होता है। तो getMin और getMax संचालन O(1) समय का उपभोग करते हैं।
यह देखना आसान है कि एक m + 1-नोड एक खाली रूट के साथ पूर्ण बाइनरी ट्री और प्रत्येक दूसरे नोड में एक तत्व एक SMMH है यदि निम्नलिखित सत्य हैं -
A1 - प्रत्येक नोड y के लिए, जिसमें एक राइट सिबलिंग है, y का एलिमेंट y के राइट सिबलिंग से कम या उसके बराबर है।
A2 - प्रत्येक नोड y के लिए जिसमें दादा-दादी है, दादा-दादी के बाएं बच्चे में तत्व y से कम या उसके बराबर है।
A3 - प्रत्येक नोड y के लिए जिसमें एक दादा-दादी है, दादा-दादी के दाहिने बच्चे में तत्व y से बड़ा या उसके बराबर है।
ध्यान दें कि यदि गुण A1 नोड y पर संतुष्ट है, तो y पर A2 और A3 में से अधिकतम एक का उल्लंघन हो सकता है। गुण A1 से A3 को लागू करते हुए हम तत्वों को सम्मिलित करने और हटाने के लिए सरल एल्गोरिदम तक पहुंचते हैं। ये एल्गोरिदम न्यूनतम और अधिकतम ढेर के लिए संबंधित एल्गोरिदम के सरल अनुकूलन हैं। उनकी जटिलता O(log m) है।
यहां, हम इन्सर्ट ऑपरेशन निर्दिष्ट करते हैं। मान लीजिए कि हम चित्र 1 के SMMH में 3 सम्मिलित करना चाहते हैं। चूंकि SMMH एक पूर्ण बाइनरी ट्री है, इसलिए हमें चित्र 2 में दर्शाई गई स्थिति में SMMH में एक नया नोड जोड़ना होगा; नए नोड को B के रूप में लेबल किया गया है।
हमारे उदाहरण में, बी एक खाली नोड को दर्शाता है। अब 3 नोड B पर डाला गया है।