部分排序问题

/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：PartSort.h
* 简要描述：部分排序
*
* 当前版本：1.0
* 作    者：raincatss
* 完成日期：2007-11-19
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/

#ifndef PARTSORT_H
#define PARTSORT_H

#define NUM_OF_RESULT 10000

typedef unsigned Type;

void PartSort(FILE *in, FILE *out, int size);

#endif /* PARTSORT_H */


/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：PartSort.c
* 简要描述：部分排序
*
* 当前版本：1.0
* 作    者：raincatss
* 完成日期：2007-11-19
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/

#include <stdio.h>
#include "PartSort.h"

static Type heap[NUM_OF_RESULT];

static void Swap(Type *p, Type *q);
static void HeapSort(int endOfHeap);
static void FilterDown(int start, int endOfHeap);

void PartSort(FILE *in, FILE *out, int size)
{
    int i;
    int endOfHeap;
    Type tmp;
    char buf[64];

    for (i=0; i<size; i++) {
        fgets(buf, sizeof(buf), in);
        sscanf(buf, "%u", &tmp);
        heap[i] = tmp;
    }

    /* create heap */
    endOfHeap = size - 1;
    for (i=(endOfHeap-1)/2; i>=0; i--) {
        FilterDown(i, endOfHeap);
    }

    while (fgets(buf, sizeof(buf), in) != NULL) {
        sscanf(buf, "%u", &tmp);
        if (tmp > heap[0]) {
            heap[0] = tmp;
            FilterDown(0, endOfHeap);
        }
    }

    HeapSort(endOfHeap);

    /* out put the result */
    for (i=0; i<size; i++) {
        fprintf(out, "%u\n", heap[i]);
    }
}

static void Swap(Type *p, Type *q)
{
    Type tmp;

    tmp = *p;
    *p = *q;
    *q = tmp;
}

static void HeapSort(int endOfHeap)
{
    int i;

    for (i=endOfHeap; i>0; i--) {
        Swap(&heap[0], &heap[i]);
        FilterDown(0, i - 1);
    }
}

static void FilterDown(int start, int endOfHeap)
{
    int i = start;
    int j = 2 * i + 1;
    Type tmp = heap[i];

    while (j <= endOfHeap) {
        if (j < endOfHeap && heap[j] > heap[j + 1])
            j++;
        if (tmp <= heap[j])
            break;
        else {
            heap[i] = heap[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    heap[i] = tmp;
}