পেয়ারিং হিপ হল একটি হিপ ডেটা স্ট্রাকচারের ধরন যা তুলনামূলকভাবে সহজ বাস্তবায়ন এবং চমৎকার প্র্যাক্টিক্যাল অ্যামোর্টাইজড পারফরম্যান্স দিয়ে সাজানো।
পেয়ারিং হিপ হিপ-অর্ডার্ড মাল্টি-ওয়ে ট্রি স্ট্রাকচার, এবং এগুলোকে সরলীকৃত ফিবোনাচ্চি হিপ হিসেবে চিহ্নিত করা যায়।
এগুলো প্রাইম অ্যালগরিদমের মতো অ্যালগরিদম বাস্তবায়নের জন্য একটি "রোবাস্ট চয়েস" হিসেবে বিবেচিত হয়, এবং নিচের অপারেশনগুলো সাপোর্ট করে (একটি মিন-হিপ ধরে):
- find-min - এই ফাংশন হিপের টপ এলিমেন্ট রিটার্ন করার দায়িত্বে থাকে।
- meld - এই ফাংশন দুটি রুট এলিমেন্ট তুলনা করে, ছোটটি ফলাফলের রুট হিসেবে থাকে, বড় এলিমেন্ট ও এর সাবট্রি এই রুটের চাইল্ড হিসেবে যোগ হয়।
- insert - এই ফাংশন ইনসার্ট করা এলিমেন্টের জন্য একটি নতুন হিপ তৈরি করে এবং মূল হিপে মেল্ড করে।
- decrease-key (ঐচ্ছিক) - এই ফাংশন কী কমাতে হলে সাবট্রি সরিয়ে, কী ছোট করে, ফলাফলটি আবার হিপে মেল্ড করে।
- delete-min - এই ফাংশন রুট মুছে, এর সাবট্রিগুলো পুনরাবৃত্তি মেল্ড করে একটি ট্রি বাকি থাকা পর্যন্ত। বিভিন্ন মার্জিং কৌশল ব্যবহৃত হয়।
- প্রতিটি নোডের লেফট চাইল্ডের দিকে একটি পয়েন্টার থাকে এবং লেফট চাইল্ড চাইল্ডের নেক্স্ট সিবলিংকে পয়েন্ট করে।
- পেয়ারিং হিপের উদাহরণ নিচে দেওয়া হলো -
পেয়ারিং হিপের টাইম কমপ্লেক্সিটি বিশ্লেষণ প্রধানত স্প্লে ট্রি থেকে অনুপ্রাণিত। প্রতি delete-min-এর অ্যামোর্টাইজড টাইম O(log n) ধরা হয়, আর find-min, meld, ও insert O(1) অ্যামোর্টাইজড টাইমে চলে।
