रैंडमाइज़्ड मेल्डेबल हीप (जिसे मेल्डेबल प्रायोरिटी क्यू भी कहा जाता है) कई सामान्य ऑपरेशन्स को सपोर्ट करता है। ये इन्सर्शन, डिलीशन, और एक खोज ऑपरेशन, findMin हैं। इन्सर्शन और डिलीशन ऑपरेशन्स को मेल्डेबल हीप के लिए विशिष्ट एक अतिरिक्त ऑपरेशन, Meld(A1, A2) के संदर्भ में लागू किया जाता है।
मेल्ड
मेल्ड (जिसे मर्ज भी कहा जाता है) ऑपरेशन का मूल लक्ष्य दो हीप्स (प्रत्येक हीप के रूट नोड्स को लेकर), A1 और A2 को लेना, उन्हें मर्ज करना, और एक सिंगल हीप नोड को परिणाम के रूप में वापस करना है। यह हीप नोड A1 और A2 पर रूटेड दो सबट्रीज के सभी एलिमेंट्स को समाहित करने वाले हीप का रूट नोड है।
इस मेल्ड ऑपरेशन की एक उत्कृष्ट विशेषता यह है कि इसे रिकर्सिवली परिभाषित किया जा सकता है। यदि कोई हीप नल मान से जुड़ा है, तो मर्ज एक खाली सेट के साथ पूरा होता है और मेथड नॉन-एम्प्टी हीप का रूट नोड लौटाता है। यदि दोनों A1 और A2 निल नहीं हैं, तो जांचें कि क्या A1 > A2। यदि हां, तो दोनों को स्वैप करें। इसलिए यह सुनिश्चित होता है कि A1 < A2 और मर्ज्ड हीप का रूट नोड A1 को समाहित करेगा। हम फिर A2 को A1.left या A1.right के साथ रिकर्सिवली मर्ज करते हैं। यह चरण वह है जहां रैंडमाइजेशन आता है क्योंकि किस साइड के साथ मर्ज करना है इसका निर्णय कॉइन टॉस द्वारा किया जाता है।
function Meld(Node A1, Node A2) if A1 is nil => return A2 if A2 is nil => return A1 if A1 > A2 => swap A1 and A2 if coin_toss is 0 => A1.left = Meld(A1.left, A2) else A1.right = Meld(A1.right, A2) return A1
इन्सर्ट
मेल्ड ऑपरेशन पूरा होने के साथ, मेल्डेबल हीप में इन्सर्ट करना बहुत सरल है। पहले, मान p को समाहित करने वाला एक नया नोड, a, बनाया जाता है। यह नया नोड फिर हीप के रूट नोड के साथ बस मर्ज हो जाता है।
function Insert(p) Node a = new Node a.p = p root = Meld(a, root) root.parent = nil increment node count
रिमूव
इन्सर्ट ऑपरेशन की तरह ही आसान, Remove() रूट नोड को हीप से हटाने के लिए मेल्ड ऑपरेशन को लागू करता है। यह रूट नोड के दो चिल्ड्रन को बस मर्ज करके और वापस किए गए नोड को नया रूट बनाकर पूरा किया जाता है।
function Remove() rootNode = Meld(rootNode.left, rootNode.right) if rootNode is not nil => rootNode.parent = nil decrement node count
FindMin
रैंडमाइज़्ड मेल्डेबल हीप के लिए संभवतः सबसे सरल ऑपरेशन, FindMin() बस हीप के रूट नोड में संग्रहीत वर्तमान एलिमेंट को लौटाता है।
अतिरिक्त ऑपरेशन्स
मेल्डेबल हीप के लिए कुछ अतिरिक्त ऑपरेशन्स जो O(log n) वर्स्ट-केस दक्षता भी रखते हैं:
- Remove(a) - नोड a और उसकी की को हीप से हटाएं।
- Absorb(P) - मेल्डेबल हीप P के सभी एलिमेंट्स को इस हीप में जोड़ें, इस प्रक्रिया में P को खाली करें।
- DecreaseKey(a, q) - नोड a में की को q तक घटाएं (प्री-कंडीशन: q ≤ a.p)।
