একটি ব্যবধান হিপ একটি এমবেডেড মিন-ম্যাক্স হিপের মতো যার প্রতিটি নোডে দুটি উপাদান থাকে। এটিকে একটি সম্পূর্ণ বাইনারি ট্রি হিসাবে সংজ্ঞায়িত করা হয় যার মধ্যে
- বাম উপাদানটি ডান উপাদানের চেয়ে ছোট বা সমান।
- উভয় উপাদানই একটি ব্যবধান সংজ্ঞায়িত করে যা বন্ধ থাকে।
- মূল ব্যতীত অন্য কোনো নোড দ্বারা উপস্থাপিত ব্যবধান হল প্যারেন্ট নোডের একটি উপ-ব্যবধান।
- বাম দিকের উপাদানগুলি একটি মিনিটের স্তূপ উপস্থাপন করে৷ ৷
- ডান দিকের উপাদানগুলি সর্বাধিক স্তূপ উপস্থাপন করে৷ ৷
উপাদানের সংখ্যার উপর নির্ভর করে, দুটি ক্ষেত্রে অনুমোদিত -
- সমস্ত উপাদানের সংখ্যা:এই ক্ষেত্রে, প্রতিটি নোডে একটি ≤ b সহ a এবং b বলে দুটি উপাদান রয়েছে। প্রতিটি নোড তারপর ব্যবধান [a, b] দ্বারা প্রতিনিধিত্ব করা হয়।
- বিজোড় সংখ্যক উপাদান:এই ক্ষেত্রে, শেষ ব্যতীত অন্য প্রতিটি নোডে ব্যবধান [a, b] দ্বারা উপস্থাপিত দুটি উপাদান রয়েছে যেখানে শেষ নোডে একটি একক উপাদান থাকবে এবং ব্যবধান [a, b] দ্বারা উপস্থাপিত হবে। .
ইন্টারভাল হিপগুলিকে একটি কৌশল প্রয়োগ করে শুরু করা যেতে পারে যা সাধারণ হিপগুলি শুরু করার জন্য ব্যবহৃত হয়--আমাদের স্তূপের নীচে থেকে মূল পর্যন্ত কাজ করুন যাতে প্রতিটি সাব ট্রিকে একটি ইন্টারভাল হিপ হিসাবে চিহ্নিত করা হয়। প্রতিটি সাব ট্রির জন্য, প্রথমে মূলের উপাদানগুলিকে অর্ডার করুন; তারপর আবার রিমুমিন ফাংশনের জন্য ব্যবহৃত রিইনসার্শন কৌশল বাস্তবায়ন করে এই সাব ট্রির রুটের বাম প্রান্ত বিন্দুটি সন্নিবেশ করুন, তারপর আবার রিমুম্যাক্স ফাংশনের জন্য ব্যবহৃত কৌশল বাস্তবায়ন করে এই সাব ট্রির রুটের ডান প্রান্তের বিন্দুটি প্রবেশ করান।
