C语言最大小堆、堆排序、获取前K大元素

旧城等待， 2022-05-18 00:20 166阅读 0赞

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;
    }