C++-এ পূর্ণসংখ্যা স্ট্রিমের মধ্যমা (Median in a Stream of Integers)

সমস্যা বিবরণ

একটি ডেটা স্ট্রিম থেকে পূর্ণসংখ্যা পড়া হচ্ছে। এ পর্যন্ত পড়া উপাদানগুলোর মধ্যমা দক্ষতার সাথে বের করতে হবে।

এলগরিদম

1. বাম পাশে একটি ম্যাক্স হিপ (Max Heap) ব্যবহার করুন যেটি কার্যকর মধ্যমার চেয়ে ছোট উপাদানগুলো ধারণ করবে, 
   এবং ডান পাশে একটি মিন হিপ (Min Heap) ব্যবহার করুন যেটি কার্যকর মধ্যমার চেয়ে বড় উপাদানগুলো ধারণ করবে।
2. প্রতিটি ইনকামিং উপাদান প্রসেস করার পর, দুটি হিপের উপাদানের সংখ্যা সর্বোচ্চ ১ দ্বারা আলাদা হতে পারে।
3. যখন দুটি হিপে সমান সংখ্যক উপাদান থাকে, তখন হিপের রুট ডেটার গড়ই কার্যকর মধ্যমা।
4. যখন হিপগুলো متعادل নয়, তখন যেই হিপে বেশি উপাদান আছে তার রুট থেকে কার্যকর মধ্যমা বেছে নেওয়া হবে।

উদাহরণ

#include <iostream>
using namespace std;

#define MAX_HEAP_SIZE 128
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

inline void Exch(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

bool Greater(int a, int b) { return a > b; }
bool Smaller(int a, int b) { return a < b; }
int Average(int a, int b) { return (a + b) / 2; }

int Signum(int a, int b) {
    if (a == b) return 0;
    return a < b ? -1 : 1;
}

class Heap {
public:
    Heap(int *b, bool (*c)(int, int)) : A(b), comp(c) { heapSize = -1; }
    virtual ~Heap() { if (A) delete[] A; }
    virtual bool Insert(int e) = 0;
    virtual int GetTop() = 0;
    virtual int ExtractTop() = 0;
    virtual int GetCount() = 0;

protected:
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * (i + 1); }
    int parent(int i) {
        if (i <= 0) return -1;
        return (i - 1) / 2;
    }
    int *A;
    bool (*comp)(int, int);
    int heapSize;

    int top() {
        int max = -1;
        if (heapSize >= 0) max = A[0];
        return max;
    }
    int count() { return heapSize + 1; }

    void heapify(int i) {
        int p = parent(i);
        if (p >= 0 && comp(A[i], A[p])) {
            Exch(A[i], A[p]);
            heapify(p);
        }
    }

    int deleteTop() {
        int del = -1;
        if (heapSize > -1) {
            del = A[0];
            Exch(A[0], A[heapSize]);
            heapSize--;
            heapify(parent(heapSize + 1));
        }
        return del;
    }

    bool insertHelper(int key) {
        bool ret = false;
        if (heapSize < MAX_HEAP_SIZE) {
            ret = true;
            heapSize++;
            A[heapSize] = key;
            heapify(heapSize);
        }
        return ret;
    }
};

class MaxHeap : public Heap {
public:
    MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) {}
    ~MaxHeap() {}
    int GetTop() { return top(); }
    int ExtractTop() { return deleteTop(); }
    int GetCount() { return count(); }
    bool Insert(int key) { return insertHelper(key); }
};

class MinHeap : public Heap {
public:
    MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) {}
    ~MinHeap() {}
    int GetTop() { return top(); }
    int ExtractTop() { return deleteTop(); }
    int GetCount() { return count(); }
    bool Insert(int key) { return insertHelper(key); }
};

int getMedian(int e, int &m, Heap &l, Heap &r) {
    int sig = Signum(l.GetCount(), r.GetCount());
    switch (sig) {
        case 1:
            if (e < m) {
                r.Insert(l.ExtractTop());
                l.Insert(e);
            } else {
                r.Insert(e);
            }
            m = Average(l.GetTop(), r.GetTop());
            break;
        case 0:
            if (e < m) {
                l.Insert(e);
                m = l.GetTop();
            } else {
                r.Insert(e);
                m = r.GetTop();
            }
            break;
        case -1:
            if (e < m) {
                l.Insert(e);
            } else {
                l.Insert(r.ExtractTop());
                r.Insert(e);
            }
            m = Average(l.GetTop(), r.GetTop());
            break;
    }
    return m;
}

void printMedian(int A[], int size) {
    int m = 0;
    Heap *left = new MaxHeap();
    Heap *right = new MinHeap();
    for (int i = 0; i < size; ++i) {
        m = getMedian(A[i], m, *left, *right);
        cout << m << endl;
    }
    delete left;
    delete right;
}

int main() {
    int A[] = {10, 20, 30};
    int size = ARRAY_SIZE(A);
    cout << "Result:\n";
    printMedian(A, size);
    return 0;
}

আউটপুট

Result:
10
15
20