सिमेट्रिक मिन-मैक्स हीप्स (SMMH)

सिमेट्रिक मिन-मैक्स हीप (SMMH)

एक **सिमेट्रिक मिन-मैक्स हीप (SMMH)** एक पूर्ण बाइनरी ट्री है जिसमें:

• **रूट खाली** होता है (कोई तत्व नहीं)।
• प्रत्येक अन्य नोड में **ठीक एक तत्व** होता है।
• कुल नोड्स = `m + 1` (जहां `m` तत्वों की संख्या है)।

संरचनात्मक गुण

किसी भी नोड y के लिए जिसके सबट्री में तत्व हैं (`elements(y) ≠ ∅`):

• लेफ्ट चाइल्ड में `elements(y)` में **न्यूनतम** तत्व होता है।
• राइट चाइल्ड (यदि मौजूद है) में `elements(y)` में **अधिकतम** तत्व होता है।

सरणी प्रतिनिधित्व और सत्यापन गुण

चूंकि SMMH एक पूर्ण बाइनरी ट्री है, यह एक सरणी में निहित रूप से संग्रहीत होता है (रूट इंडेक्स 1 पर, खाली)। तीन स्थानीय गुण SMMH को परिभाषित करते हैं:

1. A1 (सिबलिंग ऑर्डर): प्रत्येक नोड y के लिए जिसका राइट सिबलिंग है: `y.value ≤ right_sibling(y).value`।
2. A2 (ग्रैंडपेरेंट-मिन): प्रत्येक नोड y के लिए जिसका ग्रैंडपेरेंट है: `left_child(grandparent(y)).value ≤ y.value`।
3. A3 (ग्रैंडपेरेंट-मैक्स): प्रत्येक नोड y के लिए जिसका ग्रैंडपेरेंट है: `right_child(grandparent(y)).value ≥ y.value`।

नोट: यदि A1 संतुष्ट है, तो किसी नोड पर A2 और A3 में से अधिकतम एक का उल्लंघन हो सकता है।

चरम मान पहुंच

• `m = 1`: न्यूनतम = अधिकतम = रूट के लेफ्ट चाइल्ड में।
• `m > 1`: न्यूनतम = रूट का लेफ्ट चाइल्ड; अधिकतम = रूट का राइट चाइल्ड।
• `getMin()` / `getMax()`: **O(1)**।

सम्मिलन और विलोपन

• एल्गोरिदम मानक मिन/मैक्स हीप ऑपरेशन्स के सरल अनुकूलन हैं जो A1-A3 का उपयोग करते हैं।
• सम्मिलन: नया नोड ट्री के अंत में जोड़ें, A1-A3 का उपयोग करके बबल-अप करें।
• विलोपन: चरम मान को अंतिम नोड से बदलें, A1-A3 का उपयोग करके ट्रिकल-डाउन करें।
• जटिलता: **O(log m)** दोनों के लिए।

उदाहरण: 3 सम्मिलित करना

चित्र 1 (12 तत्वों) में, नया नोड B अगली पूर्ण-ट्री पोजीशन पर जोड़ा जाता है। मान 3 को B में रखा जाता है, फिर A1-A3 का उपयोग करके बबल-अप किया जाता है।