C/C++小知识点：堆排序及解题案例

• 堆排序函数的基本用法
• 大顶堆：升序排列（前K大用大顶堆）
• 小顶堆：降序排列（前K小用小顶堆）

#include 
#include 
#include 
#include 
#include    //必须引用这个头文件，否则heap函数第三个参数无法使用

template  bool comp(const T& elem1, const T& elem2)
{
    return (abs(elem1) > abs(elem2));
}

int main()
{
    std::vector vec1{-23, 14, 87, -35, 15, -36, 22, 34, 19, -49, -2, 0};
    std::vector vec2(vec1);
    std::vector vec3(vec1);

    
    std::make_heap(vec1.begin(), vec1.end(), std::less());
    while (!vec1.empty())
    {
        std::pop_heap(vec1.begin(), vec1.end(), std::less());
        printf("%d ", vec1.at(vec1.size() - 1));
        vec1.pop_back();
    }
    printf("n");       //87 34 22 19 15 14 0 -2 -23 -35 -36 -49

    
    std::make_heap(vec2.begin(), vec2.end(), std::greater());
    while (!vec2.empty())
    {
        std::pop_heap(vec2.begin(), vec2.end(), std::greater());
        printf("%d ", vec2.at(vec2.size() - 1));
        vec2.pop_back();
    }
    printf("n");       //-49 -36 -35 -23 -2 0 14 15 19 22 34 87

    
    std::make_heap(vec3.begin(), vec3.end(), comp);
    while (!vec3.empty())
    {
        std::pop_heap(vec3.begin(), vec3.end(), comp);
        printf("%d ", vec3.at(vec3.size() - 1));
        vec3.pop_back();
    }
    printf("n");       //0 -2 14 15 19 22 -23 34 -35 -36 -49 87
    return 0;
}

• 解题案例

leetcode-973题：最接近原点的K个点

class Solution {
public:
    static double originDistance(vector& point){
        return sqrt(pow(point[0], 2) + pow(point[1], 2));
    }

    static bool comp(vector& elem1, vector& elem2){
        return originDistance(elem1) > originDistance(elem2);
    }

    vector> kClosest(vector>& points, int k) {
        vector> ret;
        make_heap(points.begin(), points.end(), comp);
        while(!points.empty() && k){
            pop_heap(points.begin(), points.end(), comp);
            ret.push_back(points[points.size() - 1]);
            points.pop_back();
            k--;
        }
        return ret;
    }
};