C++-এ চলমান সংখ্যা স্ট্রিমের মধ্যমা (Median of Running Stream of Numbers in C++)

এই সমস্যাতে, আমাদের একটি ডেটা স্ট্রিম দেওয়া থাকে যা liên tục পূর্ণসংখ্যা পড়ছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা উপাদানগুলো পড়বে এবং এ 지금까지 পড়া সব উপাদানের মধ্যমা (median) গণনা করবে।

মধ্যমা (Median) কী?

একটি অ্যারে বা সিকোয়েন্সের মধ্যমা হল সর্ট করা সিকোয়েন্সের মধ্যবর্তী উপাদান (এটি আরোহী বা অবরোহী ক्रमে সাজানো হতে পারে)।

মধ্যমা গণনার নিয়ম

• বিষম সংখ্যক উপাদানের ক্ষেত্রে: মধ্যমা হল মধ্যবর্তী উপাদান।
• জোড় সংখ্যক উপাদানের ক্ষেত্রে: মধ্যমা হল দুটি মধ্যবর্তী উপাদানের গড়।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট: 3, 65, 12, 20, 1

প্রতি ইনপুটের পর সিকোয়েন্স এবং মধ্যমা:

ইনপুট - 3 : সিকোয়েন্স -(3) : মধ্যমা - 3
ইনপুট - 65 : সিকোয়েন্স -(3, 65) : মধ্যমা - 34
ইনপুট - 12 : সিকোয়েন্স -(3, 12, 65) : মধ্যমা - 12
ইনপুট - 20 : সিকোয়েন্স -(3, 12, 20, 65) : মধ্যমা - 16
ইনপুট - 1 : সিকোয়েন্স -(1, 3, 12, 20, 65) : মধ্যমা - 12

নোট: এখানে মধ্যমা গণনা সহজ করতে সর্ট করা সিকোয়েন্স ব্যবহার করা হয়েছে।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধানের জন্য একাধিক পদ্ধতি রয়েছে:

1. প্রতিটি ধাপে সর্টিং করে মধ্যমা বের করা
2. সেলফ-ব্যালেন্সিং BST (Binary Search Tree) ব্যবহার করা
3. হিপ (Heap) ব্যবহার করা - এটি সবচেয়ে কার্যকর সমাধান

ম্যাক্স-হিপ (Max-Heap) বা মিন-হিপ (Min-Heap) — যেকোনো একটি ব্যবহার করে প্রতিটি ইনসারশনের পর দ্রুত মধ্যমা বের করা যায়।

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

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

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

bool Greater(int a, int b) { return a > b; }
bool Smaller(int a, int b) { return a < b; }

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 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])) {
            swap(A[i], A[p]);
            heapify(p);
        }
    }

    int deleteTop() {
        int del = -1;
        if (heapSize > -1) {
            del = A[0];
            swap(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) {}
    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) {}
    int GetTop() { return top(); }
    int ExtractTop() { return deleteTop(); }
    int GetCount() { return count(); }
    bool Insert(int key) { return insertHelper(key); }
};

int findMedian(int e, int &median, Heap &left, Heap &right) {
    switch (Signum(left.GetCount(), right.GetCount())) {
        case 0:
            if (e < median) {
                left.Insert(e);
                median = left.GetTop();
            } else {
                right.Insert(e);
                median = right.GetTop();
            }
            break;
        case 1:
            if (e < median) {
                right.Insert(left.ExtractTop());
                left.Insert(e);
            } else {
                right.Insert(e);
            }
            median = (left.GetTop() + right.GetTop()) / 2;
            break;
        case -1:
            if (e < median)
                left.Insert(e);
            else {
                left.Insert(right.ExtractTop());
                right.Insert(e);
            }
            median = (left.GetTop() + right.GetTop()) / 2;
            break;
    }
    return median;
}

void printMedianStream(int A[], int size) {
    int median = 0;
    Heap *left = new MaxHeap();
    Heap *right = new MinHeap();
    for (int i = 0; i < size; i++) {
        median = findMedian(A[i], median, *left, *right);
        cout << "Median of elements : ";
        for (int j = 0; j <= i; j++) cout << A[j] << " ";
        cout << "is " << median << endl;
    }
}

int main() {
    int A[] = {12, 54, 9, 6, 1};
    int size = ARRAY_SIZE(A);
    printMedianStream(A, size);
    return 0;
}

আউটপুট

Median of elements : 12 is 12
Median of elements : 12 54 is 33
Median of elements : 12 54 9 is 12
Median of elements : 12 54 9 6 is 10
Median of elements : 12 54 9 6 1 is 9