堆的排序研究

今天偶然看到一个找出N个数中最大的前500个数，一个不错的解法是使用堆来进行选择，每一次读取一个数判断是否需要放到堆中，这样比较下来就可以找到最大或最小的前500个数了，自己晚上就参考别人的代码写了一个最小堆的结构，后期继续补充。

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

typedef int ElemType;
struct heap{
    ElemType *num;
    int heapsize;
    int maxSize;
};

struct heap HP;
int init_heap(int size)
{
     if(size <= 0){
            printf("not allow empty heap\n");
            return -1;
    }
    HP.num = malloc(size*sizeof(ElemType));
    if(HP.num == NULL){
            printf("malloc failed\n");
            exit(1);
    }

    HP.heapsize = 0;
    HP.maxSize = size;
    return 0;
}

void exit_heap()
{
    if(HP.num != NULL){
        free(HP.num);
        HP.num = NULL;
        HP.heapsize = 0;
        HP.maxSize = 0;
    }
}

int isEmpty()
{
    if(HP.heapsize == 0){
        return 1;
    }else{
        return 0;
    }
}

int insert_heap(ElemType arg)
{
    int ct;
    if(HP.heapsize == HP.maxSize){
        ElemType* pe;
        pe = realloc(HP.num,HP.heapsize*2*sizeof(ElemType));
        if(pe == NULL){
            printf("realloc heap failed\n");
            exit(1);
        }
        HP.num = pe;
        HP.maxSize = HP.heapsize*2;
    }
    HP.num[HP.heapsize] = arg;
    HP.heapsize++;

    ct = HP.heapsize - 1;

    while(0 != ct){
        int j = (ct - 1) /2;
        if(arg > HP.num[j])  break;
        HP.num[ct] = HP.num[j];
        ct = j;
    }
    HP.num[ct] = arg;
    return 1;
}

ElemType delete_heap()
{
      ElemType temp,x;
      int i,j;

      if(HP.heapsize == 0){
            printf("heap has been empty\n");
            exit(1);
       }

       x = HP.num[0];
       HP.heapsize--;

       if(HP.heapsize == 0){
            return x;
        }

        temp = HP.num[HP.heapsize];
        i = 0;
        j = 2*i + 1;
        while(j <= HP.heapsize-1){
            if((j< HP.heapsize-1) && (HP.num[j] > HP.num[j+1])){
                    j++;
            }
            if(temp <= HP.num[j] ){
                    break;
            }

            HP.num[i] = HP.num[j];
            i = j;
            j = 2*i + 1;
        }
        HP.num[i] = temp;
        return x;
}
int main()
{
    int i;
    ElemType it;
    printf("input:");
    for(i=0;i<10;i++){
        scanf("%d",&it);
        insert_heap(it);
    }

    for(i=0;i<10;i++){
        printf("%d ",delete_heap());
    }
    printf("\n");
    return 0;
}