简介

C++

make_heap() 将区间内的元素转化为heap.

push_heap() 对heap增加一个元素.

pop_heap() 对heap取出下一个元素.

sort_heap() 对heap转化为一个已排序群集.

C++11新增特性

is_heap 测试范围内的元素是否是一个二叉堆

is_heap_until 该函数返回有效二叉堆的最末范围。如果都有效，则返回last.也就是说，返回第一个破坏二叉堆结构元素的迭代器。

例如一个序列：9 8 7 6 10 5 9

画成堆的结构如下：

可以看到，10是第一个破坏堆结构的元素，9也是

函数

1.make_heap()

make_heap()用于把一个可迭代容器变成一个堆，默认是大顶堆。

它有三个参数。第一个参数是指向开始元素的迭代器，第二个参数是指向最末尾元素的迭代器，第三个参数是less<>()或是greater<>()，前者用于生成大顶堆，后者用于生成小顶堆，第三个参数默认情况下为less<>()，less()用于生成大顶堆。

//要使用less<int>()，以及greater<int>()，请添加头文件#include <functional>，且一定要加括号less<>()

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <functional>
using namespace std;
 
int main()
{
    vector<int> q;
 
    for (int i = 0; i < 10; i++)
    {
        q.push_back(i);
    }
 
    make_heap(q.begin(), q.end(), less<int>());
 
    for (int i = 0; i < q.size(); i++)
    {
        cout << q[i] << " ";
    }
 
    return 0;
}

2.pop_heap()

pop_heap()用于将堆的第零个元素与最后一个元素交换位置，然后针对前n - 1个元素调用make_heap()函数，它也有三个参数，参数意义与make_heap()相同，第三个参数应与make_heap时的第三个参数保持一致。

//注意:pop_heap()函数，只是交换了两个数据的位置，如果需要弹出这个数据，请记得在pop_heap()后加上q.pop_back();

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <functional>
 
using namespace std;
void display(vector<int>q)
{
    for (int i = 0; i < q.size(); i++)
    {
        cout << q[i] << " ";
    }
    cout << endl;
}
 
int main()
{
    vector<int> q;
    for (int i = 0; i < 10; i++)
    {
        q.push_back(i);
    }
    make_heap(q.begin(), q.end(), less<int>());
    display(q);
    pop_heap(q.begin(), q.end(), less<int>());
    display(q);
 
    return 0;
}

3.push_heap()

push_heap()用于把数据插入到堆中，它也有三个参数，其意义与make_heap()的相同，第三个参数应与make_heap时的第三个参数保持一致。

//在使用push_heap()前，请确保已经把数据通过q.push_back()传入q中，而不是在push_heap()后再使用q.push_back(t)！！

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <functional>
using namespace std;
void display(vector<int>q)
{
    for (int i = 0; i < q.size(); i++)
    {
        cout << q[i] << " ";
    }
    cout << endl;
}
int main()
{
    vector<int> q;
    for (int i = 0; i < 10; i++)
    {
        q.push_back(i);
    }
    make_heap(q.begin(), q.end(), less<int>());
    cout << "插入前" << endl;
    display(q);
    q.push_back(12);
    push_heap(q.begin(), q.end(), less<int>());
    cout << "插入后" << endl;
    display(q);
    return 0;
}

4.sort_heap()

sort_heap()是将堆进行排序，排序后，序列将失去堆的特性（子节点的键值总是小于或大于它的父节点）。它也具有三个参数，参数意义与make_heap()相同，第三个参数应与make_heap时的第三个参数保持一致。大顶堆sort_heap()后是一个递增序列，小顶堆是一个递减序列。

//请在使用这个函数前，确定序列符合堆的特性，否则会报错！

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <functional>
using namespace std;
void display(vector<int>q)
{
    for (int i = 0; i < q.size(); i++)
    {
        cout << q[i] << " ";
    }
    cout << endl;
}
int main()
{
    vector<int> q;
    for (int i = 0; i < 10; i++)
    {
        q.push_back(i);
    }
    make_heap(q.begin(), q.end(), less<int>());
    cout << "sort前" << endl;
    display(q);
    sort_heap(q.begin(), q.end(), less<int>());
    cout << "sort后" << endl;
    display(q);
    return 0;
}