堆
堆就是如图，像这样一种连续的数据，但是注意0的位置不存储数据，目的是为了让编号一置
这里介绍两个概念
大顶堆： 一段内存在二叉数的基础上有序（父节点大于子节点）
小顶堆：与顶堆相反
堆算法函数
make_heap 创建一个堆（默认形式大顶堆）
push_heap
入堆（不是传的数据，只是每一次调用，让你变成堆的形式），起到一个调整数据位置的作用
pop_heap 出堆，也只是一个调整数据，将数据放到堆后面
sort_heap 给堆排序
注意：真正意义上的，插入数据和删除数据，还是要根据相应的容器调用其中的函数（比如：push_back,pop_back）
堆算法函数的使用
make_heap
有三个参数，前2个参数表示迭代器的范围，最后一个参数写比较准则
#include<iostream> #include<functional> #include<algorithm> #include<vector> using namespace std; int main() { vector<int> v1 = { 1, 2, 9, 7, 9 }; make_heap(v1.begin(), v1.end());//默认形式是大顶堆 for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; make_heap(v1.begin(), v1.end(), less<int>()); //大顶堆 copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ")); cout << endl; make_heap(v1.begin(), v1.end(), greater<int>()); //小顶堆 copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ")); return 0; }
push_heap
在插入数据的时候，调用这个函数，将其变为堆的形式
#include<iostream> #include<functional> #include<algorithm> #include<vector> using namespace std; int main() { vector<int> v1 = { 1, 2, 9, 7, 9 }; make_heap(v1.begin(), v1.end());//默认形式是大顶堆 for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; v1.push_back(8); v1.push_back(4); for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; push_heap(v1.begin(), v1.end()); for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); return 0; }
pop_heap
出堆的时候，先调用这个函数，将第一个元素，放到最后面，然后用尾删法，删除数据
#include<iostream> #include<functional> #include<algorithm> #include<vector> using namespace std; int main() { vector<int> v1 = { 1, 2, 9, 7, 9 }; make_heap(v1.begin(), v1.end());//默认形式是大顶堆 for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; pop_heap(v1.begin(), v1.end()); //堆的删除 for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; v1.pop_back(); for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); make_heap(v1.begin(), v1.end()); cout << endl; for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; return 0; }
sort_heap
这个排序默认，也就是简单的从小到大排序，当然第三个参数，你应该也可以写比较准则
#include<iostream> #include<functional> #include<algorithm> #include<vector> using namespace std; int main() { vector<int> v1 = { 1, 2, 9, 7, 9 }; make_heap(v1.begin(), v1.end());//默认形式是大顶堆 for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); cout << endl; sort_heap(v1.begin(), v1.end()); for_each(v1.begin(), v1.end(), [](int& date) {cout << date << " "; }); return 0; }
