মেলডেবল প্রায়োরিটি কিউ
সংজ্ঞা
একটি র্যান্ডোমাইজড মেলডেবল হিপ (Meldable Heap বা Randomized Meldable Priority Queue) হল একটি প্রায়োরিটি কিউ-ভিত্তিক ডেটা স্ট্রাকচার যার অন্তর্নিহিত স্ট্রাকচারও একটি হিপ-অর্ডার্ড বাইনারি ট্রি। তবে, অন্তর্নিহিত বাইনারি ট্রির আকার নিয়ে কোনো কঠোর নিয়ম নেই।
সুবিধা
- এই পদ্ধতির অনেক সুবিধা রয়েছে অন্য ডেটা স্ট্রাকচারের চেয়ে।
- এটি অন্য ডেটা স্ট্রাকচারের চেয়ে সহজ পদ্ধতি প্রদান করে।
- র্যান্ডোমাইজড মেলডেবল হিপের সব অপারেশন সহজে বাস্তবায়নযোগ্য এবং তাদের কমপ্লেক্সিটি বাউন্ডের কনস্ট্যান্ট ফ্যাক্টরগুলো ছোট।
- ব্যালেন্স কন্ডিশন রক্ষা করার কোনো প্রয়োজন নেই এবং নোডের ভেতরে স্যাটেলাইট ইনফরমেশন রাখার প্রয়োজন নেই।
- শেষ পর্যন্ত, এই স্ট্রাকচার ভালো ওয়ার্স্ট-কেস টাইম ইফিশিয়েন্সি প্রদর্শন করে। অধিকাংশ ক্ষেত্রে প্রতিটি অপারেশনের এক্সিকিউশন টাইম হায় প্রোবাবিলিটিতে লগারিদমিক।
স্কিউ হিপ
স্কিউ হipas (অথবা সেলফ-অ্যাডজাস্টিং হিপ) হল একটি হিপ ডেটা স্ট্রাকচার যা বাইনারি ট্রি হিসেবে বাস্তবায়িত।
স্কিউ হিপ সুবিধাজনক কারণ এটি বাইনারি হিপের চেয়ে দ্রুত মার্জ করতে পারে।
বাইনারি হিপের বিপরীতে, এখানে কোনো স্ট্রাকচারাল কনস্ট্রেইন্ট নেই, তাই ট্রির হাইট লগারিদমিক হবে এমন কোনো গ্যারান্টি নেই।
শুধু দুটি শর্ত পূরণ করতে হয়:
- সাধারণ হিপ অর্ডার রক্ষা করতে হবে (রুট ন্যূনতম এবং সাবট্রির জন্যও রিকার্সিভলি সত্য), কিন্তু ব্যালেন্সড প্রোপার্টি (সব লেভেল ফুল হবেই শুধু লাস্ট লেভেল বাদে) দরকার নেই।
- স্কিউ হিপের মূল অপারেশন শুধু Merge। অন্যান্য অপারেশন যেমন insert, extractMin() ইত্যাদি শুধু Merge দিয়ে বাস্তবায়ন করা যায়।
উদাহরণ
প্রথম স্কিউ হিপ ধরা যাক
দ্বিতীয় হিপ ধরা যাক
এবং আমরা চূড়ান্ত মার্জড ট্রি পাই
রিকার্সিভ মেল্ড প্রসেস
merge(a1, a2) Let a1 and a2 be the two min skew heaps to be merged. Let a1's root be smaller than a2's root (If not smaller, we can swap to get the same). We swap a1->left and a1->right. a1->left = merge(a2, a1->left)
