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