मेल करने योग्य प्राथमिकता कतार संचालन

रैंडमाइज्ड मेल्डेबल हीप (जिसे मेल्डेबल प्रायोरिटी क्यू भी कहा जाता है) कई सामान्य ऑपरेशनों का समर्थन करता है। इन्हें इंसर्शन, डिलीशन और एक सर्च ऑपरेशन, फाइंडमिन के रूप में जाना जाता है। सम्मिलन और हटाने के संचालन को एक अतिरिक्त ऑपरेशन के संदर्भ में लागू किया जाता है, जो मेल करने योग्य ढेर, मेल्ड (ए 1, ए 2) के लिए विशिष्ट होता है।

पिघला

मेल्ड (मर्ज के रूप में भी कहा जाता है) ऑपरेशन का मूल लक्ष्य दो ढेर (प्रत्येक ढेर रूट नोड्स ले कर), ए 1 और ए 2 लेना है, और परिणामस्वरूप एक ही ढेर नोड लौटाते हुए उन्हें विलय करना है। यह हीप नोड एक ढेर का रूट नोड है जिसमें A1 और A2 पर रूट किए गए दो सबट्री के सभी तत्व होते हैं।

इस मेल्ड ऑपरेशन की एक उत्कृष्ट विशेषता यह है कि इसे पुनरावर्ती रूप से परिभाषित किया जा सकता है। यदि या तो ढेर शून्य मान से जुड़े हैं, तो विलय एक खाली सेट के साथ पूरा किया जाता है और विधि गैर-खाली ढेर के रूट नोड को वापस कर देती है। यदि A1 और A2 दोनों शून्य नहीं हैं, तो जांचें कि क्या A1> A2 है। अगर ऐसा है, तो दोनों को स्वैप करें। इसलिए यह सुनिश्चित किया जाता है कि A1

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

सम्मिलित करें

मेल्ड ऑपरेशन पूरा होने के साथ, मेल्डेबल हीप में डालना इतना सरल है। सबसे पहले, एक नया नोड, a, बनाया जाता है जिसमें मान p होता है। इस नए नोड को तब केवल हीप्स रूट नोड के साथ मर्ज कर दिया जाता है।

function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count

निकालें

इंसर्ट ऑपरेशन के समान ही, निकालें () हीप से रूट नोड को खत्म करने के लिए मेल्ड ऑपरेशन को लागू करता है। यह केवल रूट नोड के दो बच्चों को मिलाकर और लौटाए गए नोड को नया रूट बनाकर पूरा किया जाता है।

function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count

FindMin

रैंडमाइज्ड मेल्डेबल हीप के लिए संभवत:सबसे सरल ऑपरेशन, FindMin () हीप के रूट नोड में संग्रहीत वर्तमान तत्व को लौटाता है।

अतिरिक्त संचालन

कुछ अतिरिक्त ऑपरेशन जो मेल्डेबल हीप के लिए लागू किए जा सकते हैं जिनमें O(logn) सबसे खराब स्थिति वाली दक्षता भी होती है -

• Remove(a) - नोड a और उसकी कुंजी को हीप से हटा दें।
• Absorb(P) - पिघलने योग्य ढेर P के सभी तत्वों को इस ढेर में जोड़ दें, इस प्रक्रिया में P को खाली कर दें।
• DecreaseKey(a, q) - नोड में कुंजी को a से q तक घटाता है (पूर्व शर्त:q <=a.p).