c++ 建立大小根堆

1. 什么是堆（heap）

堆（heap）是一种数据结构，我们可以通过堆，方便的找到数据中最大或最小的数。它的pop_max操作（弹出最大值，整个堆重新heapify）算法复杂度是O(logN)

2. 如何建立一个堆

在c++中已经有建立好的数据结构，方便我们实现堆，堆本质是一种特殊的存储方式，它实质的载体是数组等一些的容器。在c++中调用 #include <queue>中的template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;

比如我们给定一组数[3,2,5,7,9,1],想让这组数构成一个大根堆，每次弹出最大的数：

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(int argc, char const *argv[]){
    // 创建默认的大根堆
    priority_queue<int> big_heap;
    big_heap.push(3);
    big_heap.push(2);
    big_heap.push(5);
    big_heap.push(7);
    big_heap.push(9);
    big_heap.push(1);

    while( !big_heap.empty()){
        cout << big_heap.top() << " , " ;
        big_heap.pop();
}
return 0;}

输出：9 , 7 , 5 , 3 , 2 , 1
在c++中默认的priority_queue就是一个大根堆，如果想要使用小根堆就要把后面的Compare写成greater比较器：

priority_queue<int, std::vector<int>, greater<int>> small_heap;

输出：1 , 2 , 3 , 5 , 7 , 9

3.特殊结构的堆

如果堆中的数据不是直接可以比较的类型（int，double，long），而是一个结构体呢？如果我们不重写Compare，将会出错 error: invalid operands to binary expression ('const student' and 'const student'){return __x < __y;}，因为student根本无法比较。
这里我们有两种方法可以改写Compare：

重载运算符 operator <

# include <queue>
# include <iostream>
# include <string>
#include <vector>
using namespace std;

struct student
{
    int id;
    string name;
    int age;
};

// 直接重载运算符 < 
bool operator< (student a, student b){
     return a.age < b.age;
}

int main(int argc, char const *argv[])
{
    /* code */
    student s1 = {1, "到处露鸟", 26};
    student s2 = {3, "尿尿不洗手", 18};
    student s3 = {2, "便秘女孩", 17};

    //priority_queue<student, std::vector<student>, cmp > students;

    priority_queue<student> students;

    students.push(s1);
    students.push(s3);
    students.push(s2);

    while(!students.empty()){
            cout << students.top().id << ',' << students.top().name << ',' << students.top().age <<endl;
        students.pop();
    }

    return 0;
}

输出：按照年龄的大根堆
1,到处露鸟,26
3,尿尿不洗手,18
2,便秘女孩,17

用结构体重载 operator（）

// 结构体重载运算符()
struct cmp
{
    bool operator()(student x, student y){
        return x.age < y.age;
    }
};

int main(int argc, char const *argv[])
{
    /* code */
    student s1 = {1, "到处露鸟", 26};
    student s2 = {3, "尿尿不洗手", 18};
    student s3 = {2, "便秘女孩", 17};
    student s4 = {5, "便秘男孩", 20};
    student s5 = {4, "露屁屁", 28};

    priority_queue<student, std::vector<student>, cmp > students;

    //priority_queue<student> students;

    students.push(s1);
    students.push(s3);
    students.push(s2);
    students.push(s5);
    students.push(s4);

    while(!students.empty()){
        cout << students.top().id << ',' << students.top().name << ',' << students.top().age <<endl;
        students.pop();
    }

    return 0;
}

输出：
4,露屁屁,28
1,到处露鸟,26
5,便秘男孩,20
3,尿尿不洗手,18
2,便秘女孩,17
第二种的原因是，在STL中的数据结构的比较是用 operator（）定义