मेल्डेबल प्रायोरिटी क्यू
परिभाषा
एक रैंडमाइज़्ड मेल्डेबल हीप (जिसे मेल्डेबल हीप या रैंडमाइज़्ड मेल्डेबल प्रायोरिटी क्यू भी कहा जाता है) एक प्राथमिकता कतार आधारित डेटा स्ट्रक्चर है जिसमें अंतर्निहित संरचना भी एक हीप-ऑर्डर्ड बाइनरी ट्री है। हालांकि, अंतर्निहित बाइनरी ट्री के आकार पर कोई कठोर नियम नहीं हैं।
लाभ
- इस दृष्टिकोण में समान डेटा स्ट्रक्चर पर कई सुविधाएं यानी लाभ हैं।
- यह अन्य डेटा स्ट्रक्चर की तुलना में सरल दृष्टिकोण प्रदान करता है।
- रैंडमाइज़्ड मेल्डेबल हीप के सभी ऑपरेशन्स लागू करने में आसान हैं और उनकी जटिलता सीमाओं में कॉन्स्टेंट फैक्टर छोटे हैं।
- बैलेंस कंडीशन्स को बनाए रखने की कोई आवश्यकता नहीं है और नोड्स के भीतर कोई सैटेलाइट जानकारी आवश्यक नहीं है।
- अंत में, यह संरचना अच्छी वर्स्ट-केस समय दक्षता प्रदर्शित करती है। ज्यादातर प्रत्येक व्यक्तिगत ऑपरेशन का निष्पादन समय उच्च संभावना के साथ लॉगरिदमिक होता है।
स्क्यू हीप
एक स्क्यू हीप (या सेल्फ-एडजस्टिंग हीप) को एक हीप डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है जिसे बाइनरी ट्री के रूप में लागू किया जाता है।
स्क्यू हीप फायदेमंद हैं क्योंकि वे बाइनरी हीप की तुलना में अधिक तेजी से मर्ज करने में सक्षम हैं।
बाइनरी हीप के विपरीत, कोई संरचनात्मक प्रतिबंध नहीं हैं, इसलिए इस बात की कोई गारंटी नहीं है कि ट्री की ऊंचाई लॉगरिदमिक है।
केवल दो शर्तों को पूरा किया जाना चाहिए:
- सामान्य हीप ऑर्डर बनाए रखा जाना चाहिए (रूट न्यूनतम है और वही सबट्रीज के लिए रिकर्सिवली सच है), लेकिन बैलेंस्ड प्रॉपर्टी (सभी लेवल अंतिम को छोड़कर भरे होने चाहिए) की आवश्यकता नहीं है।
- स्क्यू हीप में मुख्य ऑपरेशन केवल मर्ज है। हम मर्ज से जुड़े अन्य ऑपरेशन्स जैसे इन्सर्ट, एक्सट्रैक्टमिन(), आदि को लागू कर सकते हैं।
उदाहरण
मान लीजिए स्क्यू हीप 1 है:

दूसरा हीप माना जाता है:

और हमें अंतिम मर्ज्ड ट्री इस रूप में प्राप्त होती है:

रिकर्सिव मर्ज प्रक्रिया
merge(a1, a2) Let a1 and a2 be the two min skew heaps to be merged. Let a1’s root be smaller than a2’s root (If not smaller, we can swap to get the same). We swap a1->left and a1->right. a1->left = merge(a2, a1->left)