目录

堆排序

快速排序比堆排序好

215. 数组中的第K个最大元素

数据流——703. 数据流中的第 K 大元素

347. 前 K 个高频元素

堆排序

堆排序_guanlovean的博客-CSDN博客_堆排序

堆的构建， 以及堆排序的c++实现_pursue_my_life的博客-CSDN博客_堆排序c++实现

1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；

2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；

3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。

4、 最后，就得到一个有序的序列了。

任意一个队列

 

1. 首先我们将现在的无序序列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。

 

2. 将无序序列构建成一个大顶堆。

        根据大顶堆的性质，每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点，也就是非叶子节点，然后调整他们的父子关系，非叶子节点遍历的顺序应该是从下往上，这比从上往下的顺序遍历次数少很多，因为，大顶堆的性质要求父节点的值要大于或者等于子节点的值，如果从上往下遍历，当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候，因为子节点还没有遍历到，所以子节点不符合大顶堆性质，当子节点调整后，必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点，因为当前节点调整完之后，当前节点必然比它的所有子节点都大，所以，只会影响到子节点二次调整。相比之下，从下往上的遍历方式比从上往下的方式少了父节点的二次调整。

 

3. 排序序列，将堆顶的元素值和尾部的元素交换。

4. 然后将剩余的元素重新构建大顶堆，其实就是调整根节点以及其调整后影响的子节点，因为其他节点之前已经满足大顶堆性质。

5. 序列排序完成

 

#include 
using namespace  std;

//判断是否符合大根堆，调整大根堆
void adjust_heap(int* a, int  father, int len)
{
    int left = 2 * father;
    int right = left + 1;
    int max = father;  //假设根为最大的
    
    if(left <= len && a[left] > a[max])
        max = left;
    if(right <= len && a[right] > a[max])
        max = right;  //将最大的值的位置存进max
    
    if(max != father)
    {
        swap(a[max] , a[father]);  //将最大的结点放在父亲结点
        adjust_heap(a , max , len);  // 调整被影响到的结点
    }
}

//排序
void heap_sort(int* a, int len)
{
    //1. 建树 ， 将初始化的序列全部元素排列为大根堆
    for(int i = len/2 - 1;i >= 0; i--)  //从第一个非叶子结点开始调整
        adjust_heap(a , i , len);

    //2. 堆排序，此时需要排列的长度为len，逐渐减小
    for(int i = len - 1 ; i > 0;i--)
    {
        swap(a[i] , a[0]);  //将堆顶元素与最后一个元素交换
        adjust_heap(a , 0 , i - 1);  
        //调整根节点 1 以及其调整后影响的子节点
        //因为其他节点之前已经满足大顶堆性质。
    }
}

int main()
{
    int a[11] = {1, 7, 3, 4, 5, 2, -22, -1, 10, 0, 9};
    int len = sizeof(a) / sizeof(int);
    cout << len << endl;

    //将根节点设为1 ，第一个非叶子结点为len/2
    for(int i = 0;i < len;i++)
    {
        cout << a[i] << ' ';
    }
    cout << endl;  //未排序序列

    heap_sort(a , len);  //排序

    for(int i = 0;i < len;i++)
    {
        cout << a[i] << ' ';
    }
    cout << endl;  //已排序序列

    return 0;
}

 

快速排序比堆排序好

为什么说快速排序是性能最好的排序算法？_chenmeiqi777的博客-CSDN博客_最快的排序算法

[C++][Leetcode][TopK]前K大问题+前K高频(堆+map)_D.Guan的博客-CSDN博客

在大规模数据的时候，快速排序只会线性增长，而堆排序增加幅度很大，会远远大于线性。堆排序指针寻址会耗费很多时间，但是快速排序的话只是移动到前后位置。

​

215. 数组中的第K个最大元素

C++中sort的时间复杂度为nlongn

排序排序有一个partion函数，设定一个哨兵，每次把一个数组分成两部分，前部分小于哨兵元素（或者大于)，后部分大于哨兵元素（或者小于）。这样每次调用一次partion函数就可以将一个元素放在其应该在的位置上。我们要求取的是第K大的元素，我们并不关心前k-1个元素是否有序。所以我们可以采用partion函数来寻找第K大的元素。按照通常的解法，我们选取第一个元素作为哨兵。经过一轮partion，如果当前元素的下标小于k-1,表示我们要找的第K大的元素在当前元素的后半部分，否则反之。这样我们最多调用K次partion就可以找到第K大的元素，时间复杂度为Klogn。

class Solution {
public:

    void partion(vector& nums , int left , int right,int k)
    {
        if(left < right)
        {
            int privot = nums[left];  //选取第一个元素作为哨兵
            int i = left;
            int j = right;

            while(i != j)
            {
                while(i < j && nums[j] <= privot)
                    j--;
                if(i < j)
                {
                    nums[i] = nums[j];
                }

                while(i < j && nums[i] > privot)
                    i++;
                if(i < j)
                {
                    nums[j] = nums[i];
                }
            }

            nums[i] = privot;
            if(i < k - 1)
            {
                partion(nums , i + 1 , right,k);
            }
            else if(i > k - 1)
            {
                partion(nums , left , i - 1, k);
            }
            else 
                return ;
        }
    }
    int findKthLargest(vector& nums, int k) {
        int n = nums.size();
        if(n <= 0 || n < k)
            return 0;

        partion(nums , 0 , n - 1, k);
        return nums[k - 1];        
    }
};

数据流——703. 数据流中的第 K 大元素

既然不知道有多少数，我们就想到了堆。我们只需要维护一个大小为K的最小堆，那么堆定元素就是第K大的元素。最小堆的堆顶元素小于堆里的其他元素。使用STL的优先队列构建堆。

class KthLargest {
public:
    priority_queue , greater > q;  //小根堆，存储前k大的元素
    int k;

    KthLargest(int k, vector& nums) {
        this -> k = k;
        for(auto& x : nums)
            add(x);
    }
    
    int add(int val) {
        q.push(val);
        if(q.size() > k)  //如果大于k个就抛出最小的一个
            q.pop();
        return  q.top();
    }
};

347. 前 K 个高频元素

第一种思路：使用map存储元素以及其出现的频数。创建一个vector存储map里的元素对。根据第二个元素的大小进行进行降序排序，然后返回前K个元素即可。
第二种思路：使用map存储元素以及其出现的频数。维护一个最小堆，大小为K，存储的元素为map里的元素对。然后返回这个最小堆里的元素即可。

关于C++ pair 和make_pair的用法_张卫建的博客-CSDN博客_make_pair

class Solution {
public:
    struct cmp{
        bool operator()(const pair&a ,const pair&b) {
                return a.second > b.second;
            }
        };

    vector topKFrequent(vector& nums, int k) {
        map m;  //存储元素及其出现的频数
        vector res;   //存储map里面的元素对
        priority_queue , vector> , cmp> q;   //大根堆里面存放
        for(int i = 0; i < nums.size();i++)  
        {
            m[nums[i]]++;
        }

        int map_size = m.size();

        map::iterator it;
        for(it = m.begin();it != m.end();it++)  //存储K个的pair数据
        {
            if(q.size() < k)
                q.push(make_pair(it->first,it->second));
            else
            {
                if(q.size() == k & q.top().second < it -> second)
                {
                    q.pop();
                    q.push(make_pair(it->first,it->second));
                }
            }
        }

        while( !q.empty())  //将最后剩下来的K个pair存进vector数组 
        {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }
};