寻找数组中最小的k个数。keywords:堆，自上而下，自下而上

mink.c

/*
 * =========================================================
 *       Filename:  mink.c
 *    Description:  输入n个整数,找出其中最小的K个数
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
#define PARENT(i) (i - 1) / 2
#define LEFT(i) (2*i + 1)
#define RIGHT(i) (2*i + 2)
#define SWAP(x , y) do{int temp; temp = x; x = y; y = temp;}while(0)
#define HTOP 0
typedef struct heap{
    int *array;
    int size;
    int len;
}Heap ,*pHeap;

void heapInitial(Heap **h ,int k);
//Heap *heapInitial(int k);
void heapPush(pHeap h , int data);
void heapPrint(pHeap h);
int main(){
    int n , k ,i;
    Heap *h = NULL;
    while(scanf("%d%d",&n ,&k) == 2){
        heapInitial(&h , k);
//        heapInitial(k);
        for(int j =0; j < n ; j++){
            scanf("%d",&i);
            //建堆
            heapPush(h , i);
//            heapPrint(h);
        }
        heapPrint(h);
    }
}

void heapInitial(Heap **h ,int k){
    pHeap p;
    p = (Heap *)malloc(sizeof(Heap));
    p->size = k;
    p->array= malloc(sizeof(int) * k);
    p->len = 0;
    *h = p;
}
//Heap *heapInitial(int k){
//    pHeap p;
//    p = malloc(sizeof(Heap));
//    p->size = k;
//    p->array = malloc(k * sizeof(int));
//    p->len = 0;
//    return p;
//}
void heapPush(pHeap h , int data){
    if (h->len == h->size){//大根堆满的情况
        int top = 0; //堆顶位置
        if (data < h->array[top]){
            h->array[top] = data;
            int p = top;
            int max;
            while(p <= h->len/2 ){
                max = p;
                if(LEFT(p) < h->len && h->array[LEFT(p)] > h->array[max])
                    max = LEFT(p);
                if(RIGHT(p) < h->len && h->array[RIGHT(p)] > h->array[max])
                    max = RIGHT(p);
                if (max == p)
                    break;
                else{
                    SWAP(h->array[p] , h->array[max]);
                    p = max;
                }
            }
        }
    }
    else{
        int p = h->len;
        h->array[p] = data;
        while(p > 0 && h->array[p] > h->array[PARENT(p)]){
            SWAP(h->array[p] , h->array[PARENT(p)]);
            p = PARENT(p);
        }
        ++(h->len);
    }
}
void heapPrint(pHeap h){
    for(int i = 0; i < h->len ; i++)
        printf("%d%s",h->array[i],(i == h->len -1)?"\n":" ");
    free(h);
}