Median_of_Data_Stream.png
/**
* Abstract: To be added
*/
typedef struct PriorityQueueStruct {
int capacity;
int count;
double *keys;
double(*cmp)(double, double);
}*PriorityQueue;
void pq_exch(double *a, int i, int j) {
double t = a[I];
a[i] = a[j];
a[j] = t;
}
int pq_max(double *a, int i, int j, double(*cmp)(double, double)) { return cmp(a[i], a[j]) > .0f ? i : j; }
void pq_swim(double *a, int k, double (*cmp)(double, double)) {
int p = k / 2;
while (k > 1 && cmp(a[k], a[p]) > .0f) {
pq_exch(a, k, p);
k = p;
p = k / 2;
}
}
void pq_sink(double *a, int n, int k, double(*cmp)(double, double)) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && cmp(a[j], a[j + 1]) < .0f) j += 1;
if (cmp(a[k], a[j]) >= .0f) break;
pq_exch(a, k, j);
k = j;
}
}
PriorityQueue PriorityQueueCreate(double(*cmp)(double, double)) {
PriorityQueue pq = (PriorityQueue)malloc(sizeof(*pq));
pq->cmp = cmp;
pq->capacity = 20000;
pq->count = 0;
pq->keys = malloc((pq->capacity + 1) * sizeof(double));
return pq;
}
void PriorityQueueRelease(PriorityQueue pq) {
free(pq->keys);
free(pq);
}
bool PriorityQueueIsEmpty(PriorityQueue pq) { return pq->count == 0; }
void PriorityQueueInsert(PriorityQueue pq, double k) {
pq->keys[++pq->count] = k;
pq_swim(pq->keys, pq->count, pq->cmp);
}
double PriorityQueueDelete(PriorityQueue pq) {
double ret = pq->keys[1];
pq->keys[1] = pq->keys[pq->count];
pq->keys[pq->count] = INT_MIN;
pq->count--;
pq_sink(pq->keys, pq->count, 1, pq->cmp);
return ret;
}
double PriorityQueueHP(PriorityQueue pq) { return pq->keys[1]; }
double ascending_cmp(double a, double b) { return b - a; }
double descending_cmp(double a, double b) { return a - b; }
typedef struct {
PriorityQueue leftPQ;
PriorityQueue rightPQ;
} MedianFinder;
/** initialize your data structure here. */
MedianFinder* medianFinderCreate() {
MedianFinder *mf = (MedianFinder*)malloc(sizeof(*mf));
mf->leftPQ = PriorityQueueCreate(descending_cmp);
mf->rightPQ = PriorityQueueCreate(ascending_cmp);
return mf;
}
void medianFinderAddNum(MedianFinder* mf, double num) {
if (mf->leftPQ->count != 0 && mf->rightPQ->count != 0) {
if (mf->leftPQ->count > mf->rightPQ->count) {
double min = PriorityQueueHP(mf->leftPQ);
if (num < min) {
PriorityQueueDelete(mf->leftPQ);
PriorityQueueInsert(mf->leftPQ, num);
PriorityQueueInsert(mf->rightPQ, min);
} else {
PriorityQueueInsert(mf->rightPQ, num);
}
} else {
double min = PriorityQueueHP(mf->leftPQ);
if (num <= min) {
PriorityQueueInsert(mf->leftPQ, num);
} else {
min = PriorityQueueHP(mf->rightPQ);
if (min >= num) {
PriorityQueueInsert(mf->leftPQ, num);
} else {
PriorityQueueDelete(mf->rightPQ);
PriorityQueueInsert(mf->rightPQ, num);
PriorityQueueInsert(mf->leftPQ, min);
}
}
}
} else if (mf->leftPQ->count == 0) {
PriorityQueueInsert(mf->leftPQ, num);
} else if (mf->rightPQ->count == 0) {
double min = PriorityQueueHP(mf->leftPQ);
if (num < min) {
PriorityQueueDelete(mf->leftPQ);
PriorityQueueInsert(mf->leftPQ, num);
PriorityQueueInsert(mf->rightPQ, min);
} else {
PriorityQueueInsert(mf->rightPQ, num);
}
}
}
double medianFinderFindMedian(MedianFinder* mf) {
if (mf->leftPQ->count > mf->rightPQ->count) {
return PriorityQueueHP(mf->leftPQ);
} else {
return (PriorityQueueHP(mf->leftPQ) + PriorityQueueHP(mf->rightPQ)) / 2.0f;
}
}
void medianFinderFree(MedianFinder* mf) {
PriorityQueueRelease(mf->leftPQ);
PriorityQueueRelease(mf->rightPQ);
free(mf);
}
网友评论