C 언어 최대 소량, 정렬, 앞 K 요소 가져오기

void littleHeapfy(double *pdData, long lIdx, long lLen)
{
    long lLeft = 0, lRight = 0, lSwap = 0;
    double dTmp = 0.0;

    lLeft = lIdx;
    lRight = lIdx;

    if (2 * lIdx <= lLen)
    {
        lLeft = 2 * lIdx;
    }

    if (2 * lIdx + 1 <= lLen)
    {
        lRight = 2 * lIdx + 1;
    }

    lSwap = lRight;

    if (pdData[lRight] > pdData[lLeft])
    {
        lSwap = lLeft;
    }

    if (pdData[lSwap] < pdData[lIdx])
    {
        dTmp          = pdData[lIdx];
        pdData[lIdx]     = pdData[lSwap];
        pdData[lSwap] = dTmp;
        littleHeapfy(pdData, lSwap, lLen);
    }

    return;
}

void buildLittleHeap(double *pdData, long lLen)
{
    long i = 0;

    for (i = lLen / 2 + 1; i >= 1; i--)
    {
        littleHeapfy(pdData, i, lLen);
    }

    return;
}

void bigHeapfy(double *pdData, long lIdx, long lLen)
{
    long lLeft = 0, lRight = 0, lSwap = 0;
    double dTmp = 0.0;

    lLeft = lIdx;
    lRight = lIdx;

    if (2 * lIdx <= lLen)
    {
        lLeft = 2 * lIdx;
    }

    if (2 * lIdx + 1 <= lLen)
    {
        lRight = 2 * lIdx + 1;
    }

    lSwap = lRight;

    if (pdData[lRight] < pdData[lLeft])
    {
        lSwap = lLeft;
    }

    if (pdData[lSwap] > pdData[lIdx])
    {
        dTmp          = pdData[lIdx];
        pdData[lIdx]  = pdData[lSwap];
        pdData[lSwap] = dTmp;
        bigHeapfy(pdData, lSwap, lLen);
    }

    return;
}

void buildBigHeap(double *pdData, long lLen)
{
    long i = 0;

    for (i = lLen / 2 + 1; i >= 1; i--)
    {
        bigHeapfy(pdData, i, lLen);
    }

    return;
}

/*   pdData  lBegin lEnd   iMth     */
double calcMthMax(double *pdData, long lBegin, long lEnd, int iMth)
{
    double *pdSortData = NULL, dMax =  0.0;
    long i = 0;

    dMax = pdData[lBegin];

    if ((iMth > lEnd - lBegin) ||
        (iMth <= 0))
    {
        return dMax;
    }

    pdSortData = (double *)malloc((iMth + 1) * sizeof(double));

    if (NULL != pdSortData)
    {
        memset(pdSortData, 0, (iMth + 1)*sizeof(double));

        for (i = 0; i < iMth; i++)
        {
            pdSortData[i + 1] = pdData[lBegin + i];
        }

        buildLittleHeap(pdSortData, iMth);

        for (i = lBegin + iMth; i < lEnd; i++)
        {
            if (pdData[i] > pdSortData[1])
            {
                pdSortData[1] = pdData[i];
                littleHeapfy(pdSortData, 1, iMth);
            }
        }

        dMax = pdSortData[1];
        free(pdSortData);
    }

    return dMax;
}

/*   pdData  lBegin lEnd   iMth     */
double calcMthMin(double *pdData, long lBegin, long lEnd, int iMth)
{
    double *pdSortData = NULL, dMax =  0.0;
    long i = 0;

    if (lBegin < 0)
        return 0.0;

    dMax = pdData[lBegin];

    if ((iMth > lEnd - lBegin) ||
        (iMth <= 0))
    {
        return dMax;
    }

    pdSortData = (double *)malloc((iMth + 1) * sizeof(double));

    if (NULL != pdSortData)
    {
        memset(pdSortData, 0, sizeof((iMth + 1)*sizeof(double)));

        for (i = 0; i < iMth; i++)
        {
            pdSortData[i + 1] = pdData[lBegin + i];
        }

        buildBigHeap(pdSortData, iMth);

        for (i = lBegin + iMth; i < lEnd; i++)
        {
            if (pdData[i] < pdSortData[1])
            {
                pdSortData[1] = pdData[i];
                bigHeapfy(pdSortData, 1, iMth);
            }
        }

        dMax = pdSortData[1];
        free(pdSortData);
    }

    return dMax;
}

double calcMaxOpt(double *pdData, long lBegin, long lEnd, int iMth)
{
    double dMax;
    int iTotalNum = (lEnd - lBegin + 1);

    if (iMth < ceil(iTotalNum / 2))
    {
        dMax = calcMthMax(pdData, lBegin, lEnd, iMth);
    }
    else
    {
        dMax = calcMthMin(pdData, lBegin, lEnd, iTotalNum - iMth);
    }

    return dMax;
}