堆

堆的動態創建與刪除可參考http://blog.csdn.net/pngynghay/article/details/22101359，此處不再贅述。

雙堆求中位數

算法描述：

1、創建兩個堆（一個小根堆、一個大根堆），堆大小至少為給定數據個數的一半，(size+1)/2，即向上取整；

2、假定變量mid用來保存中位數，取定第一個元素，賦值給mid，即作為初始的中位數；

3、依次遍歷後面的每一個數據，如果比mid小，則插入大根堆；否則插入小根堆；

4、如果大根堆和小根堆上的數據個數相差為2，則將mid插入到元素個數較少的堆中，然後從元素個數較多的堆中刪除根節點，並將跟節點賦值給mid；

5、重復步驟3和4，直到所有的數據遍歷結束；

此時，mid保存了一個數，再加上兩個堆中保存的數，就構成了給定數據的集合。

如果兩個堆中元素個數相等，則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 < maxelem)
	{
        printf("\nmid[ %d ] = ( mid [ %d ]+maxheap->element[0][ %d ] )/2 = %d\n",mid, mid, 
			minheap->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;
}

測試結果