【数据结构】找出N个数据中最大的前k个数据（利用堆排序）

傷城~ 2022-07-12 13:10 190阅读 0赞

我们举例，假若从10000万个数里选出前100个最大的数据。

首先我们先分析：既然要选出前100个最大的数据，我们就建立一个大小为100的堆（建堆时就按找最大堆的规则建立，即每一个根节点都大于它的子女节点），然后再将后面的剩余数据若符合要求就插入堆中，不符合就直接丢弃该数据。

那我们现在考虑：确定是该选择最大堆的数据结构还是最小堆的数据结构呢。

分析一下：  
若选用最大堆的话，堆顶是堆的最大值，我们考虑既然要选出从10000万个数里选出前100个最大的数据，我们在建堆的时候，已经考虑了最大堆的特性，那这样的话最大的数据必然在它顶端。假若真不巧，我开始的前100个数据中已经有这10000个数据中的最大值了，那对于我后面剩余的10000-100的元素再想入堆是不是入不进去了！！！所以，选用最大堆从10000万个数里选出前100个最大的数据只能找出一个，而不是100个。

那如果选用最小堆的数据结构来解决，最顶端是最小值，再次遇到比它大的值，就可以入堆，入堆后重新调整堆，将小的值pass掉。这样我们就可以选出最大的前K个数据了。言外之意，假若我们要找出N个数据中最小的前k个数据，就要用最大堆了。

代码实现

#define _CRT_SECURE_NO_WARNINGS 1 
    #include<iostream> 
    using namespace std;  
    
    #include<assert.h> 
    
    void AdjustDown(int* a, int parent, int size)  
    {  
        int child = 2 * parent + 1;  
        while (child < size)  
        {  
            if (child + 1 < size && a[child] > a[child + 1])  
            {  
                child++;  
            }  
            if (a[parent]>a[child])  
            {  
                swap(a[parent], a[child]);  
                parent = child;  
                child = 2 * parent + 1;  
            }  
            else  
            {  
                break;  
            }  
        }  
    }  
    
    
    void Print(int* a, int size)  
    {  
        cout << "前k个最大的数据：" << endl;  
        for (int i = 0; i < size; i++)  
        {  
            cout << a[i] << " ";  
        }  
        cout << endl;  
    }  
    
    
    int* HeapSet(int*a,int N,int K)  
    {  
        assert(a);  
        assert(K > 0);  
        int* arr = new int[K];  
        //将前K个数据保存 
        for (int i = 0; i < K; i++)  
        {  
            arr[i] = a[i];  
        }  
    
        //建堆 
        for (int i = (K-2)/2; i >=0; i--)  
        {  
            AdjustDown(arr,i,K);  
        }   
    
        //对剩余的N-K个元素比较大小 
        for (int i = K; i < N; i++)  
        {  
            if (arr[0]<a[i])  
            {  
                arr[0] = a[i];  
                AdjustDown(arr, 0, K);  
            }  
        }  
    
        return arr;  
        delete[] arr;  
    }  
    
    
    void Test()  
    {  
        int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67, 25, 178 };  
        int k = 5;  
        int* ret = HeapSet(arr, sizeof(arr) / sizeof(arr[0]), k);  
        Print(ret, k);   
    }  
    
    
    int main()  
    {  
        Test();  
        system("pause");  
        return 0;  
    }

由此可以看出，时间复杂度为：Ｋ＋（Ｋ-2）/２\*lgn＋（Ｎ－Ｋ）\*lgn –＞ O(N)  
空间复杂度为：K–>O(1)。  
本文出自 “Han Jing’s Blog” 博客，请务必保留此出处[http://10740184.blog.51cto.com/10730184/1768075][http_10740184.blog.51cto.com_10730184_1768075]

[http_10740184.blog.51cto.com_10730184_1768075]: http://10740184.blog.51cto.com/10730184/1768075