Trung vị trong luồng số nguyên (số nguyên chạy) trong C++

Đề bài

Cho các số nguyên được đọc từ một luồng dữ liệu. Tìm trung vị của các phần tử đã đọc cho đến nay một cách hiệu quả.

Sau khi đọc phần tử thứ 1 của luồng - 10 -> trung vị - 10

Sau khi đọc phần tử thứ 2 của luồng - 10, 20 -> trung vị - 15

Sau khi đọc phần tử thứ 3 của luồng - 10, 20, 30 -> trung vị - 20, và cứ thế...

Thuật toán

1. Sử dụng max heap ở bên trái để biểu diễn các phần tử nhỏ hơn trung vị hiệu quả, và min heap ở bên phải để biểu diễn các phần tử lớn hơn trung vị hiệu quả.
2. Sau khi xử lý một phần tử đến, số lượng phần tử trong hai heap khác nhau tối đa 1 phần tử.
3. Khi cả hai heap chứa cùng số lượng phần tử, ta lấy trung bình của dữ liệu gốc của hai heap làm trung vị hiệu quả.
4. Khi các heap không cân bằng, ta chọn trung vị hiệu quả từ gốc của heap chứa nhiều phần tử hơn.

Ví dụ

#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 << "Kết quả:\n";
    printMedian(A, size);
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên, nó sẽ tạo ra đầu ra sau:

Kết quả: 10 15 20