হিপ ও প্রায়োরিটি কিউপড়তে ৫ মিনিট লাগবে

টু-হিপ প্যাটার্ন (Two-Heap Pattern)

সংখ্যার পাহাড়কে মাঝখান থেকে দুই ভাগ করা — সবসময় চোখের পলকে মিডিয়ান বা মাঝের সংখ্যা বের করা

add number: O(log n)find median: O(1)space: O(n)

অগোছালো অনেকগুলো সংখ্যার ভেতর থেকে মিডিয়ান (Median) বা একদম মাঝখানের সংখ্যাটা বের করতে হলে প্রথমে সবগুলোকে ছোট থেকে বড় হিসেবে সাজাতে (Sort) হয়, যাতে O(n log n) সময় লাগে। কিন্তু ধরুন, আপনাকে একটার পর একটা নতুন সংখ্যা দেওয়া হচ্ছে এবং প্রতিবার নতুন সংখ্যা আসার পরই আপনাকে মাঝের সংখ্যাটা বা মিডিয়ান বলতে হবে। তখন কী করবেন?

এই সমস্যার জাদুকরী সমাধান হলো টু-হিপ প্যাটার্ন (Two-heap pattern)। ভেবে দেখুন, একটা লম্বা লাইনকে যদি ঠিক মাঝখান থেকে দুভাগ করা যায়: তাহলে বাঁ দিকের অর্ধেক লাইনের সবাই ডান দিকের অর্ধেকের চেয়ে উচ্চতায় ছোট হবে। আমরা এখানে ঠিক সেই কাজটাই দুটো হিপ (Heap) দিয়ে করি:

ম্যাক্স-হিপ (Max-heap / নিচের অর্ধেক): এই হিপের রুট বা মাথায় সবসময় সবচেয়ে বড় সংখ্যাটা বসে থাকে — এটাই হলো আমাদের মিডিয়ানের বাঁ দিকের সংখ্যা।
মিন-হিপ (Min-heap / ওপরের অর্ধেক): এই হিপের রুট বা মাথায় সবসময় সবচেয়ে ছোট সংখ্যাটা বসে থাকে — এটাই হলো আমাদের মিডিয়ানের ডান দিকের সংখ্যা।

এখন মিডিয়ান বের করাটা একদম ডালভাত: যদি মোট সংখ্যা বিজোড় হয়, তবে যেই হিপটা একটু বড়, তার রুটই হলো মিডিয়ান। আর জোড় হলে, দুই হিপের রুটের গড় (Average) করলেই মিডিয়ান পাওয়া যায়।

যে দুটো নিয়ম বা শর্ত মানতেই হবে

প্রতিটা নতুন সংখ্যা ঢোকানোর পর আপনাকে দুটো শর্ত অক্ষরে অক্ষরে পালন করতে হবে:

সাইজ ঠিক রাখা (Size balance): |max_heap.size - min_heap.size| ≤ 1 — অর্থাৎ দুই হিপের সাইজের পার্থক্য যেন কোনোভাবেই ১-এর বেশি না হয়।
মান ঠিক রাখা (Value ordering): max_heap.top() ≤ min_heap.top() — ম্যাক্স-হিপের রুট বা সবচেয়ে বড় সংখ্যাটা যেন কখনোই মিন-হিপের সবচেয়ে ছোট সংখ্যাটার চেয়ে বড় না হয়ে যায় (নিচের অর্ধেকের কেউ যেন ওপরের অর্ধেকের চেয়ে বড় না হয়)।

◈ Watch two-heap pattern

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

অ্যালগরিদমটা দেখতে যেমন

pseudocode

class MedianFinder:
    def __init__(self):
        self.lo = []  # ম্যাক্স-হিপ (পাইথনের জন্য মাইনাস দিয়ে সেভ করতে হয়)
        self.hi = []  # মিন-হিপ

    def addNum(self, num):
        # ধাপ ১: ম্যাক্স-হিপে পুশ করুন (নিচের অর্ধেক)
        heapq.heappush(self.lo, -num)

        # ধাপ ২: মান ঠিক রাখুন — নিশ্চিত করুন যেন lo.top <= hi.top হয়
        if self.hi and (-self.lo[0]) > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))

        # ধাপ ৩: সাইজের ব্যালান্স ঠিক করুন
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]  # বিজোড় সংখ্যা: নিচের অর্ধেকের কাছে একটা বেশি আছে
        return (-self.lo[0] + self.hi[0]) / 2.0  # জোড় সংখ্যা: দুই রুটের গড় বের করুন

একটা হিপ না দিয়ে দুটো কেন?

একটামাত্র হিপ আপনাকে শুধু একদিকের চরম ভ্যালু (হয় সবচেয়ে ছোট, নয়তো সবচেয়ে বড়) O(1) স্পিডে দিতে পারে। কিন্তু মিডিয়ান থাকে একেবারে মাঝখানে, যা একটা হিপ কখনোই চট করে দিতে পারে না। দুটো হিপ ডেটাকে এমনভাবে দুভাগ করে ফেলে, যেন ওই মাঝখানের দুপাশের দুই সীমানাই হিপের রুট বা মাথায় চলে আসে — যার ফলে আপনি সবসময় O(1) স্পিডে মিডিয়ান পেয়ে যান।

নতুন ভ্যারিয়েন্ট: স্লাইডিং উইন্ডো মিডিয়ান (Sliding window median)

LeetCode 480-তে এই প্যাটার্নটাই একটু ঘুরিয়ে দেওয়া হয়েছে: উইন্ডো বা ফ্রেম এগোবে, সংখ্যা যোগ হবে, আবার পেছনের সংখ্যা বাদও পড়বে। এখানেও ওই একই টু-হিপ ইনভ্যারিয়েন্ট বা নিয়ম মানতে হয়। আর পুরোনো সংখ্যা মোছার জন্য 'লেজি ডিলিশন' (Lazy deletion — সংখ্যাটাকে শুধু মার্ক করে রাখা, আর একদম রুটে চলে এলে তবেই মুছে ফেলা) ব্যবহার করলে স্পিড সবসময় O(log n)-এ আটকে থাকে।

দ্রষ্টব্য: যখনই কোনো প্রশ্নে 'চলমান মিডিয়ান (running median)', 'ডেটা স্ট্রিমের মিডিয়ান', বা পরিবর্তনশীল ডেটার 'k-তম পার্সেন্টাইল' বের করতে বলা হবে — চোখ বন্ধ করে ধরে নেবেননন এটা টু-হিপ প্যাটার্নের প্রশ্ন। এটা O(n log n) সময়ের সাধারণ সর্টিংয়ের কাজকে জাস্ট O(n log n) সময়ে নামিয়ে আনে, আর বারবার মিডিয়ান খোঁজার কাজকে O(1) করে দেয়।