题解 | #数据流中的中位数#

typedef struct Heap {
    int* context;
    int size;//当前个数
    int capacity;//最大个数
} Heap;

Heap* heap_max;
Heap* heap_min;

void heap_adjust_up_min(Heap* heap, int child);//上根堆上滤
void heap_adjust_down_min(Heap* heap, int root);//小根堆下滤（用于pop）
void heap_adjust_up_max(Heap* heap, int child);//大根堆上滤
void heap_adjust_down_max(Heap* heap, int root);//大根堆下滤（pop）
void swap(int* a,int*b){
    int temp=*a;
    *a=*b;
    *b=temp;
}

void heap_min_push(Heap* heap, int n) {
    if (heap->size == heap->capacity) {
        heap->context = (int*)realloc(heap->context,
                                      ((heap->capacity + 1) * 2 - 1) * sizeof(int));
        heap->capacity = (heap->capacity + 1) * 2 - 1;
    }

    heap->context[heap->size] = n;
    heap->size++;
    heap_adjust_up_min(heap, heap->size - 1);
}

void heap_max_push(Heap* heap, int n) {
    if (heap->size == heap->capacity) {
        heap->context = (int*)realloc(heap->context,
                                      ((heap->capacity + 1) * 2 - 1) * sizeof(int));
        heap->capacity = (heap->capacity + 1) * 2 - 1;
    }

    heap->context[heap->size] = n;
    heap->size++;
    heap_adjust_up_max(heap, heap->size - 1);
}

void heap_adjust_up_min(Heap* heap, int child) {
    int parent = (child - 1) / 2;//最后加入节点的父亲节点
    int temp;

    while (child > 0) {
        if (heap->context[parent] > heap->context[child]) {
            //父亲节点大，小根堆上滤
            swap(&heap->context[parent] , &heap->context[child]);
            child = parent;
            parent = (child - 1) / 2;
        } else break;
    }
}

void heap_adjust_up_max(Heap* heap, int child) {
    int parent = (child - 1) / 2;
    int temp;

    while (child > 0) {
        if (heap->context[parent] < heap->context[child]) {
            swap(&heap->context[parent] , &heap->context[child]);

            child = parent;
            parent = (child - 1) / 2;
        } else break;
    }
}

void heap_pop_min(Heap* heap) {
    //堆的根和最后一个节点交换
    swap(&heap->context[0],&heap->context[heap->size - 1]);
    --heap->size;//节点数--；
    heap_adjust_down_min(heap, 0);
}

void heap_pop_max(Heap* heap) {
    swap(&heap->context[0],&heap->context[heap->size - 1]);
    --heap->size;
    heap_adjust_down_max(heap, 0);
}

void heap_adjust_down_min(Heap* heap, int root) {
    int parent = root;
    int child = parent * 2 + 1; // 第一个子节点

    while (child < heap->size) {
        //选出最小的child节点数
        if (child + 1 < heap->size && heap->context[child + 1] < heap->context[child])
            ++child;
        //父亲节点大就交换
        if (heap->context[parent] > heap->context[child]) {
            swap(&heap->context[parent],&heap->context[child]);
            parent = child;
            child = parent * 2 + 1;
        } else break;
    }
}

void heap_adjust_down_max(Heap* heap, int root) {
    int parent = root;
    int child = parent * 2 + 1; // 第一个子节点

    while (child < heap->size) {
        if (child + 1 < heap->size && heap->context[child + 1] > heap->context[child])
            ++child;

        if (heap->context[parent] < heap->context[child]) {
            swap(&heap->context[parent],&heap->context[child]);
            parent = child;
            child = parent * 2 + 1;
        } else break;
    }
}

Heap* init_heap(Heap* heap, int first) {
    heap = (Heap*)malloc(sizeof(Heap));
    heap->size = 0;
    heap->capacity = 1;
    heap->context = (int*)malloc(sizeof(int));
    heap->context[0] = first;
    return heap;
}

void Insert(int num) {
    // write code here
    if (heap_max == NULL || heap_min == NULL) {
        heap_min = init_heap(heap_min, -100000);
        heap_max = init_heap(heap_max, 100000);
    }

    heap_min_push(heap_min, num);
    //不让小根堆数超过大根堆
    if (heap_min->size > heap_max->size) {
        heap_max_push(heap_max, heap_min->context[0]);
        heap_pop_min(heap_min);
    } 
    else if (heap_min->size == heap_max->size) {
        //小根堆的数必须>大根堆的数
        if (heap_min->context[0] < heap_max->context[0]) {
            heap_max_push(heap_max, heap_min->context[0]);
            heap_pop_min(heap_min);
            heap_min_push(heap_min, heap_max->context[0]);
            heap_pop_max(heap_max);
        }
    }
}

double GetMedian() {
    // write code here
    double result;
    if (heap_min->size < heap_max->size) result = (double)heap_max->context[0];
    else result = ((double)heap_max->context[0] + (double)heap_min->context[0]) /2.0;
    return result;
}