在这个问题中，我们得到了一个连续读取整数的数据流。我们的任务是创建一个程序，该程序将读取元素并计算这些元素的中值。
数组的中值是排序序列中的中间元素（可以是升序或降序）。
对于奇数，中位数是中间元素
对于偶数，中位数是两个中间元素的平均值
让我们举个例子来了解这个问题，
输入-3、65、12、20、1
在每个输入处
Input - 3 : sequence -(3) : median - 3 Input - 65 : sequence -(3, 65) : median - 34 Input - 12 : sequence -(3, 12, 65) : median - 12 Input - 20 : sequence -(3, 12, 20, 65) : median - 16 Input - 1 : sequence -(1, 3, 12, 20, 65) : median - 12
我们在这里使用排序的序列来简化中位数计算。
为了解决此问题，我们有多种解决方案，它们在每一步都使用排序，然后找到中位数，创建自平衡BST或使用堆。堆似乎是找到中位数的最有前途的解决方案。max-heap或min-heap均可为我们提供每次插入的中位数，也是一种有效的解决方案。
显示我们解决方案实施情况的程序，
#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(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]) ) {
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 {
private:
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{
private:
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