数据结构-堆的应用（TopK &堆排）

忘是亡心i 2022-06-05 10:50 227阅读 0赞

#### 关于堆相关的基本概念以及上调和下调的操作实现参考[http://blog.csdn.net/sssssuuuuu666/article/details/78629000][http_blog.csdn.net_sssssuuuuu666_article_details_78629000]。接下来总结下堆的应用。 ####

--------------------

#### **一：TopK问题** ####

##### 假设有这样一个问题：现在有一场整个国家都要参加的的考试，我需要找出成绩最高的三个成绩。 #####

##### 简单分析下，如果是整个国家都要参加的考试，那么数据量一定很大，假设我们电脑只有4G的内存，那么只能存放42亿九千万个字节，也就是10亿左右个整型，一个成绩给一个int类型的话，是远远不够的。这时候就考虑用堆来解决，具体思路如下： #####

##### <1>创建一个k大小的小堆,将数据前k个push进去，进行调堆； #####

##### <2>遍历剩下所有的数据，只要当遍历到的数据大于堆顶的数据(堆里最小的),那么我们让堆顶数据等于遍历到的数据；**每次堆顶数据改变，进行一次向下调整。** #####

## ![这里写图片描述][SouthEast]![这里写图片描述][SouthEast 1]![这里写图片描述][SouthEast 2] ##

#### 实现代码如下： ####

#define _CRT_SECURE_NO_WARNINGS 1
    #include <iostream>
    #include <assert.h>
    #include <vector>
    using namespace std;
    
    
    //给parent,调整child,再循环.注意构建的是小堆
    void AdjustDown(vector<int>& heap,int parent)
    {
        assert(parent < heap.size());
        int child = parent * 2 + 1;
        while (child < heap.size())
        {
            if (child + 1 < heap.size() && heap[child + 1] < heap[child])
                child++;
            if (heap[child] < heap[parent])
            {
                swap(heap[child], heap[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
                break;
        }
    }
    
    
    void TopK(const vector<int>& v, int k)
    {
        assert(k < v.size());
    
        vector<int> topK;
        topK.reserve(k);
    
        //先构建一个k元素的堆，再进行调整
        for (int i = 0; i < k; i++)
            topK.push_back(v[i]);
    
        for (int i = (k - 2)/2; i >= 0; i--)
            AdjustDown(topK,i);
    
        //遍历所有元素，进行比较调整
        for (int i = k; i < v.size(); i++)
        {
            if (v[i] > topK[0])
            {
                topK[0] = v[0];
                AdjustDown(topK,0);
            }
        }
    
        for (int i = 0; i < k; i++)
        {
            cout << topK[i] << " ";
        }
    
    }
    
    void Test1()
    {
        vector<int> v;
        v.resize(10, 5);
    
        v[4] = 100;
        v[5] = 101;
        v[6] = 102;
        v[7] = 103;
    
        TopK(v,5);
    }
    
    int main()
    {
        Test1();
    
        system("pause");
        return 0;
    }

#### **小结：** ####

##### 找最大前k个值，建小堆，如果遍历的值大于堆顶元素值，则入堆，进行调整操作，否则遍历下一个；找最小的前K个值，建大堆，如果遍历的值小于堆顶元素值，则入堆调整。 #####

--------------------

#### **二：堆排序问题** ####

##### 思路：若需要使排完的结果是顺序增长的，第一步：需要先将给定数据放入小堆进行调整；第二步：给定一个end记录最后一个元素的下标，将此元素与头交换，再次对头元素下标进行调整，重复次步骤，需要注意的是：由于每次一开始我们将堆头也就是最小的元素放入了最后，之后的调整时就不能对其进行影响，所以end每次要减一 。 #####

--------------------

![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

--------------------

#### 实现如下： ####

#define _CRT_SECURE_NO_WARNINGS 1
    #include <iostream>
    using namespace std;
    
    void AdjustDown(int* a, int sz, int parent)
    {
        int child = parent * 2 + 1;
        while (child < sz)
        {
            if (child + 1 < sz && a[child + 1] > a[child])
                child++;
            if (a[child] > a[parent])
            {
                swap(a[child], a[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
                break;
        }
    }
    
    //small to large 若从小到大排，创建大堆
    void STLHeapSort(int* a, int sz)
    {
        //先调整顺序为大堆
        for (int i = (sz - 2) / 2; i >= 0; i--)
        {
            AdjustDown(a, sz, i);
        }
        size_t end = sz - 1;
    
    
        while (end > 0)
        {
            swap(a[0], a[end]);
            AdjustDown(a, end, 0);
            --end;
        }
    }
    
    
    void Print(int* a, int sz)
    {
        for (int i = 0; i < sz; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    
    void Test()
    {
        int a[] = { 2,5,3,10 };
    
        STLHeapSort(a, sizeof(a) / sizeof(a[0]));
        Print(a, sizeof(a) / sizeof(a[0]));
    }
    
    int main()
    {
        Test();
        system("pause");
        return 0;
    }

#### **小结：** ####

##### 结果从小到大排，建大堆；从大到小排，建小堆；每次调整完end– ! 否则就前功尽弃了。 #####

[http_blog.csdn.net_sssssuuuuu666_article_details_78629000]: http://blog.csdn.net/sssssuuuuu666/article/details/78629000
[SouthEast]: https://img-blog.csdn.net/20171125142734942?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3Nzc3N1dXV1dTY2Ng==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20171125142746379?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3Nzc3N1dXV1dTY2Ng==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220605/cbb97001f35042478ecc8c54d99652e5.png
[SouthEast 3]: /images/20220605/9e32c6b557b64a069d8737feac7f618f.png
[SouthEast 4]: /images/20220605/689c6705745b491a8d49301776782543.png