贴一段100万前100的代码

Question

//100万个数取出前100名。n是100万，m是100。
template <typename T>
void heapSort(T arr[], int n, int m)
{
    for (int i = (m-1)/2; i >=0; i--)
    {
        __shiftDown(arr , m , i);
    }
    //只维护前100名
    for (int i = m; i < n; ++i)
    {
        if (arr[m] > arr[0])
        {
            swap(arr[m], arr[0]);
            __shiftDown(arr , m , 0);
        }
    }
    //排序
    for (int i = 0; i < m; ++i)
    {
        swap(arr[0] , arr[m-i]);
        __shiftDown(arr, m-i , 0);
    }

}

Answer 1

liuyubobobo 2017-04-04 02:09:11

其实只需要做一个大小为100的堆就可以哦。比如要找n=100万个元素的最大的m=100个元素，只需要维护一个大小为100的最小堆。将100万个元素的前100个元素塞进堆里之后，后面的元素都和最小堆里的最小元素作比较，如果比当前最小堆的最小元素还要小，直接扔掉；否则，将最小堆里的最小元素扔掉，新元素进堆。这样操作后，最后最小堆里剩下的100个元素，就是这100万个元素里最大的100个元素。时间复杂度是：O(nlogm) :-)

• 提问者 慕粉3197494 #1

  非常感谢！

• lobby #2

  他的代码不就是一个大小为100的堆吗

Answer 2

lobby 2020-03-29 13:41:22

//只维护前100名

    for (int i = m; i < n; ++i)

    {

        if (arr[m] > arr[0])

        {

            swap(arr[m], arr[0]);

            __shiftDown(arr , m , 0);

        }

    }

这段写的有问题吧