মেলডেবল প্রায়োরিটি কিউ অপারেশন

র‍্যান্ডোমাইজড মেলডেবল হিপ (Meldable Priority Queue之稱) অনেক সাধারণ অপারেশন সাপোর্ট করে। এগুলো হল ইনসারশন, ডিলিশন, এবং একটি সার্চিং অপারেশন findMin। ইনসারশন ও ডিলিশন অপারেশন মেলডেবল হিপের জন্য নির্দিষ্ট একটি অতিরিক্ত অপারেশন, Meld(A1, A2) দিয়ে বাস্তবায়ন করা হয়।

Meld

মেলড (মার্জও বলা হয়) অপারেশনের মূল লক্ষ্য হল দুটি হিপ (প্রতিটির রুট নোড নিয়ে), 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

Insert

মেলড অপারেশন কমপ্লিট হলে, মেলডেবল হিপে ইনসার্ট করা খুব সহজ। প্রথমে, একটি নতুন নোড, a, মান p ধারণ করে তৈরি করা হয়। এই নতুন নোডটি হিপের রুট নোডের সাথে সাদামতে মার্জ করা হয়।

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

Remove

ইনসার্ট অপারেশনের মতো সহজেই, 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)।