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