মেলডেবল অগ্রাধিকার সারি অপারেশন

র্যান্ডমাইজ করা মেলডেবল হিপ (যাকে মেলডেবল প্রায়োরিটি কিউও বলা হয়) বেশ কয়েকটি সাধারণ ক্রিয়াকলাপকে সমর্থন করে। এগুলি সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধান অভিযান, FindMin নামে পরিচিত। সন্নিবেশ এবং মুছে ফেলার ক্রিয়াকলাপগুলি মেল্ডেবল হিপ, মেল্ড(A1, A2) এর জন্য নির্দিষ্ট একটি অতিরিক্ত অপারেশনের পরিপ্রেক্ষিতে প্রয়োগ করা হয়।

মেল্ড

মেল্ড (যাকে একত্রীকরণও বলা হয়) অপারেশনের মূল লক্ষ্য হল দুটি হিপ (প্রতিটি হিপস রুট নোড গ্রহণ করে), A1 এবং A2, এবং সেগুলিকে একত্রিত করা, ফলে একটি একক হিপ নোড ফিরিয়ে দেওয়া। এই হিপ নোড হল একটি স্তূপের রুট নোড যেখানে 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

সরান

সন্নিবেশ অপারেশনের মতোই সহজ, Remove() হিপ থেকে রুট নোড বাদ দিতে মেল্ড অপারেশন প্রয়োগ করে। এটি শুধুমাত্র রুট নোডের দুটি সন্তানকে মেলড করে এবং ফিরে আসা নোডটিকে নতুন রুট হিসাবে তৈরি করার মাধ্যমে সম্পন্ন করা হয়৷

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 এবং এর কী সরান।
শোষন(P) - এই স্তূপে মেলডেবল হিপ P-এর সমস্ত উপাদান যোগ করুন, প্রক্রিয়ায় P খালি করুন।
DecreaseKey(a, q) - a থেকে q পর্যন্ত নোডের কী হ্রাস করে (প্রি-কন্ডিশন:q <=a.p)।