使用最小堆求第K大的数

练手代码，codepad.org已验证。

该算法为海量数据的求第k大的数的解法之一。

建立大小为k的最小堆，每输入一个数，如果比堆顶大，那么替换堆顶元素，然后维护最小堆的特性。

堆顶元素即为第k大的数。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define LEFT(a) ((a)<<1)+1
#define RIGHT(a) ((a)<<1)+2
#define SWAP(a,b) a^=b;b^=a;a^=b;

int heapcount;
int* initialHeap(int k){
    int * heap = (int*)malloc(sizeof(int)*k);
    heapcount = 0;
    return heap;
}
void MinHeapify(int *heap, int heapsize, int tar){
    assert(heap!=NULL);
    int min = tar;
    if(RIGHT(tar)<heapsize && heap[RIGHT(tar)] < heap[min])
        min = RIGHT(tar);
    if(LEFT(tar)<heapsize && heap[LEFT(tar)] < heap[min])
        min = LEFT(tar);
    if(min != tar){
         SWAP(heap[min],heap[tar]);
         MinHeapify(heap, heapsize, min);
    }
}
void buildHeap(int *input, int k){
    assert(input!=NULL);
    int i;
    for(i = (k-1)>>1 ; i>=0; i--){
        MinHeapify(input, k, i);
    }
}
void append(int *heap, int k, int cur){
    assert(heap!=NULL);
    if(heapcount<k){
        heap[heapcount++] = cur;
        if(heapcount == k){
            buildHeap(heap,k);
            heapcount++;
            }
        }
    else{
        if(cur>heap[0]){
            heap[0] = cur;
            MinHeapify(heap,k,0);
        }
    }
}



int main(){
    int k = 3;
    int input[] = {3,1,5,7,3,4,9,4,10};
    int *heap = initialHeap(k);
    int i;
    for(i = 0;i<sizeof(input)/sizeof(int);i++){
        append(heap, k, input[i]);
    }
    printf("finial = %d \n", heap[0]);
}