ค่ามัธยฐานในสตรีมจำนวนเต็ม (จำนวนเต็มที่ทำงานอยู่) ใน C++

ข้อความของปัญหา

กำหนดให้จำนวนเต็มถูกอ่านจากสตรีมข้อมูล หาค่ามัธยฐานขององค์ประกอบที่อ่านมาแล้วในวิธีที่มีประสิทธิภาพ

หลังจากอ่านองค์ประกอบแรกของสตรีม - 10 -> ค่ามัธยฐาน - 10

หลังจากอ่านองค์ประกอบที่สองของสตรีม - 10, 20 -> ค่ามัธยฐาน - 15

หลังจากอ่านองค์ประกอบที่สามของสตรีม - 10, 20, 30 -> ค่ามัธยฐาน - 20, และต่อไป...

อัลกอริทึม

1. ใช้ Max Heap ด้านซ้ายเพื่อแทนองค์ประกอบที่น้อยกว่าค่ามัธยฐานที่มีผล และ Min Heap ด้านขวาเพื่อแทนองค์ประกอบที่มากกว่าค่ามัธยฐานที่มีผล
2. หลังจากประมวลผลองค์ประกอบที่เข้ามา จำนวนองค์ประกอบใน Heap ทั้งสองจะต่างกันสูงสุด 1 องค์ประกอบ
3. เมื่อทั้งสอง Heap มีจำนวนองค์ประกอบเท่ากัน เราจะเลือกค่าเฉลี่ยของข้อมูลรากของ Heap เป็นค่ามัธยฐานที่มีผล
4. เมื่อ Heap ไม่สมดุล เราจะเลือกค่ามัธยฐานที่มีผลจากรากของ Heap ที่มีองค์ประกอบมากกว่า

ตัวอย่างโค้ด

#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(void){
        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{
private:
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{
private:
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;
}

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

ผลลัพธ์

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้ -

Result: 10 15 20