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