堆

堆的動態建立與刪除可參考 此處，不再贅述。

雙堆求中位數演算法描述

1. 建立兩個堆（一個小根堆、一個大根堆），堆大小至少為給定資料個數的一半，即 (size+1)/2（向上取整）。
2. 假定變數 mid 保存中位數，取第一個元素賦值給 mid 作為初始中位數。
3. 依序遍歷後續每個資料：若比 mid 小，插入大根堆；否則插入小根堆。
4. 若大根堆與小根堆資料個數相差為 2，將 mid 插入元素較少的堆，再從元素較多的堆刪除根節點並將其值賦給 mid。
5. 重複步驟 3、4 直到所有資料遍歷結束。此時 mid 加上兩堆中的資料構成原資料集合。
6. 若兩堆元素個數相等，mid 即為最終中位數；否則，元素較多堆的根節點與 mid 求平均值為最終中位數。

演算法實現（整數版）

uint32_t getmedian(uint32_t *array, uint32_t size) {
    int i = 0, minelem = 0, maxelem = 0;
    uint32_t mid = array[0];
    uint32_t heapsize = (size + 1) / 2;
    heap_t *minheap = heap_malloc(heapsize);
    heap_t *maxheap = heap_malloc(heapsize);

    for (i = 1; i < size; i++) {
        if (array[i] < mid) {
            maxheap_insert(maxheap, array[i]);
            maxelem++;
        } else {
            minheap_insert(minheap, array[i]);
            minelem++;
        }
        if (minelem - maxelem > 1) {
            maxheap_insert(maxheap, mid);
            mid = minheap->element[0];
            minheap_delete(minheap);
            maxelem++;
            minelem--;
        }
        if (maxelem - minelem > 1) {
            minheap_insert(minheap, mid);
            mid = maxheap->element[0];
            maxheap_delete(maxheap);
            minelem++;
            maxelem--;
        }
    }
    printf("\nmaxelem = %d, minelem = %d, pre_mid = %d\n", maxelem, minelem, mid);
    if (minelem > maxelem) {
        printf("\nmid[ %d ] = ( mid [ %d ] + minheap->element[0][ %d ] ) / 2 = %d\n",
               mid, mid, minheap->element[0], (mid + minheap->element[0]) / 2);
        mid = (mid + minheap->element[0]) / 2;
    }
    if (maxelem > minelem) {  // 原代碼有誤，應為 maxelem > minelem
        printf("\nmid[ %d ] = ( mid [ %d ] + maxheap->element[0][ %d ] ) / 2 = %d\n",
               mid, mid, maxheap->element[0], (mid + maxheap->element[0]) / 2);
        mid = (mid + maxheap->element[0]) / 2;
    }
    heap_free(minheap);
    heap_free(maxheap);
    return mid;
}

測試程式

#define NUM 10
int main() {
    uint32_t array[NUM] = {2, 20, 13, 18, 15, 8, 3, 5, 4, 25};
    getmedian(array, NUM);
    printf("\n");
    return 0;
}

測試結果