本节我们将介绍 STL 中的 priority_queue 容器，堆的使用。

注：本节内容主要参考了C 语言中文网的内容。

priority_queue 容器

priority_queue 是一个使元素有序排列的队列容器。默认队列头部的元素优先级最高。因为是一个队列，所以只能访问其第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们。
例如一个医院中等待救治的病人队列，那么病人病情的严重性便是优先级了；操作系统进程调度中，OS 也会给不同的进程赋予不同的优先级，这也可以看作是一个有着优先级的队列。

priority_queue 模板有 3 个参数，其中两个有默认的参数。
第一个参数是存储对象的类型，第二个参数是存储元素的底层容器，第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。因此模板类型是:

template <typename T, typename Container = vector<T>, typename Compare = less<T>> class priority_queue

从而，priority_queue 实例默认有一个 vector 容器。函数对象类型 less<T> 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面。
fonction 中定义了 greater<T>，用来作为模板的最后一个参数对元素排序，最小元素会排在队列前面。当然，如果指定了模板的最后一个参数，就必须提供另外的两个模板类型参数。

priority_queue 容器

priority_queue 的创建

生成一个空的整型优先级队列：

priority_queue<int> data;

可以用相同类型的对象初始化一个优先级队列

vector<int> data_{0,1,2,3,4};
vector<int>::iterator begin_iter_ = begin(data_);
auto end_iter_ = end(data_);
priority_queue<int> data{begin_iter_,end_iter_};

初始化列表中的序列可以来自于任何容器，并且不需要有序，当然类型得一致。优先级队列会对它们进行排序。

拷贝构造函数会生成一个和现有对象同类型的 priority_queue 对象，它是现有对象的一个副本。例如：

priority_queue<int> copy_data{data};

也可以使用带右值引用参数的拷贝构造函数，它可以移动一个实参对象。

当对容器内容反向排序时，最小的元素会排在队列前面，这时候需要指定 3 个模板类型参数，如下所示。

vector<int> data_{0,1,2,3,4};
vector<int>::iterator begin_iter_ = begin(data_);
auto end_iter_ = end(data_);
priority_queue<int,vector<int>,greater<int>> data{begin_iter_,end_iter_};

此时会通过使用 operator>() 函数对 int 对象进行比较，进而生成一个优先级队列，因此这会和它们在队列中的顺序相反。

优先级队列可以使用任何容器来保存元素，只要容器有成员函数 front()，push_back()，pop_back()，size()，empty()。显然包含了 deque 容器，因此这里也可以用 deque 来代替：

vector<int> data_{0,1,2,3,4};
vector<int>::iterator begin_iter_ = begin(data_);
auto end_iter_ = end(data_);
priority_queue<int,deque<int>> data{begin_iter_,end_iter_};

这个 data 优先级队列在 deque 容器中保存了一些 data vector 中的字符串，这里使用默认的比较断言，因此队列中的元素会和上面 data 中元素的顺序相同。priority_queue 构造函数会生成一个和第二个类型参数同类型的容器来保存元素，这也是 priority_queue 对象的底层容器。

可以生成 vector 或 deque 容器，然后用它们来初始化 priority_queue。下面是以 vector 的元素作为初始值来生成 priority_queue 对象：

vector<int> data_{0,4,1,2,3};
priority_queue<int> data {less<int>(),data_};

priority_queue 构造函数的第一个参数是一个用来对元素排序的函数对象，第二个参数是一个提供初始元素的容器。在队列中用函数对象对 vector 元素的副本排序。values 中元素的顺序没有变，但是优先级队列中的元素顺序变为：4 3 2 1 0。优先级队列中用来保存元素的容器是私有的，因此只能通过调用 priority_queue 对象的成员函数来对容器进行操作。
构造函数的第一个参数是函数对象类型，它必须和指定的比较模板类型参数相同，函数对象类型默认是 less<T>。如果想使用不同类型的函数，需要指定全部的模板类型参数。例如：

vector<int> data_{0,4,1,2,3};
priority_queue<int,vector<int>,greater<int>> data {greater<int>(),data_};

第三个类型参数是一个比较对象类型。如果要指定这个参数，必须指定前两个参数——元素类型和底层容器类型。

priority_queue 操作

我们来简单使用一些函数。

vector<int> data_{0,1,2};
vector<int>::iterator begin_iter_ = begin(data_);
auto end_iter_ = end(data_);
priority_queue<int> data{begin_iter_,end_iter_};
for(auto d : data_){
    data.push(d);
}
cout<<"data : "<<data.size()<<endl;
while(!data.empty()){
    cout<<data.top()<<" ";
    data.pop();
}
cout<<endl<<"data : "<<data.size()<<endl;

priority_queue 和 queue 有相同的限制。
priority_queue 没有迭代器。如果想要访问全部的元素，比如说，列出或复制它们，会将队列清空。
打印的内容为：

data : 6
2 2 1 1 0 0
data : 0

堆

堆（heaps）是一种特殊的数据组织方式，STL 中的 priority_queue 容器适配器底层就是采用堆来组织数据存储的。
为了理解什么是堆，树，这里贴张图 ：

图片.png

对于二叉树，在往期的博客中有对于二叉树常见操作的 C++ 实现系列。

堆 (Heap) 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
小顶堆：父节点总是小于或等于子节点。
大顶堆：父节点总是大于或等于子节点。

堆的创建

创建堆的函数在头文件 <algorithm> 中。max_heap() 对随机访问迭代器指定的一段元素重新排列，生成一个堆。默认使用的是 < 运算符，可以生成一个大顶堆。如：

vector<int> number{5,0,1,3,4,2,6};
vector<int>::iterator begin_iter = begin(number);
auto end_iter = end(number);
make_heap(begin_iter,end_iter);

在没有调用 make_heap() 之前，number 的内容为：

{5 0 1 3 4 2 6}

调用 make_heap() 之后，number 的内容重新排序。

{6 4 5 3 0 2 1}

number 的内容在 vector 中如下：

图片.png

堆所表示的树。

图片.png

priority_queue 是一个堆。在底层，一个 priority_queue 实例创建了一个堆。在堆中，所有成对的连续元素不需要有相同的比较关系。

上图所示堆中的前 2 个元素是顺序递减的，但第 3 个元素却大于第 2 个元素。既然如此，为什么 STL 有 priority_queue (它是一个堆)，却还需要创建堆，特别是还需要将堆作为优先级队列？

这是因为 priority_queue 有着堆没有的优势，它可以自动保持元素的顺序；但不能打乱 priority_queue 的有序状态，因为除了第一个元素，我们无法直接访问它的其他元素。如果需要的是一个优先级队列，这一点非常有用。

从另一方面来说，使用 make_heap() 创建的堆可以提供一些 priority_queue 没有的优势：

1. 可以访问堆中的任意元素，而不限于最大的元素，因为元素被存储在一个容器中，就像是我们自己的 vector。这也提供了偶然破坏元素顺序的可能，但是总可以调用 make_heap() 来还原堆。
2. 可以在任何提供随机访问迭代器的序列容器中创建堆。这些序列容器包括普通数组，string 对象，自定义容器。这意味着无论什么时候需要，都可以用这些序列容器的元素创建堆，必要时，可以反复创建。甚至还可以为元素的子集创建堆。

如果使用保持堆顺序的函数，那么可以将堆当作优先级队列使用。

这里还有另一个版本的 make_heap()，它有第 3 个参数，可以用来指定一个比较函数用于堆的排序。通过定义一个大于运算符函数，可以生成一个小顶堆。这里可以使用 functional 中的断言。例如：

vector<int> number{5,0,1,3,4,2,6};
vector<int>::iterator begin_iter = begin(number);
auto end_iter = end(number);
make_heap(begin_iter,end_iter,greater<>());

调用 make_heap() 后，number 的内容为：

{0 3 1 5 4 2 6}

可以将模板类型参数指定为 greater。这里的这个尖括号为空的版本推断并返回了类型参数。已经有一个用 make_heap() 函数在容器中生成的堆。可以在它上面进行很多操作，下面我们来深入了解这些操作。

堆的操作

堆不是容器，而是组织容器元素的一种特别方式。只能确定堆的范围，即开始和结束迭代器指定的范围。这意味着可以用容器中的元素子序列创建堆。可以在已生成的堆中添加元素。

乍一看，algorithm 头文件中的函数模板 push_heap() 创建堆的方式可能会有些奇怪。为了向堆中添加元素，首先可以用任何方法将元素附加到序列中。然后调用 push_heap() 来插入最后一个元素，为了保持堆的结构，这个元素会被重新排列到一个适当的位置。

vector<int> number{5,0,1,3,4,2,6};
vector<int>::iterator begin_iter = begin(number);
auto end_iter = end(number);
make_heap(begin_iter,end_iter);
// number : 6 4 5 3 0 2 1
// 堆的结果未改变
number.push_back(7);
// number : 6 4 5 3 0 2 1 7
// 调用 push_heap() 来插入最后一个元素，保持堆的结构
begin_iter = begin(number);
end_iter = end(number);
push_heap(begin_iter,end_iter);
// number : 7 6 5 4 0 2 1 3

注释显示了每个操作执行后的效果。必须以这种方式向堆中添加元素。只能通过调用成员函数向 number 中添加新元素，而且这个成员函数只接受迭代器作为参数，不能直接以元素作为参数。

push_back() 会在序列末尾添加元素，然后使用 push_heap() 恢复堆的排序。
通过调用 push_heap()，释放了一个信号，指出我们向堆中添加了一个元素，这可能会导致堆排序的混乱。push_heap() 会因此认为最后一个元素是新元素，为了保持堆结构，会重新排列序列。

从上面这个示例可以看出，重新排列是有必要的。我们注意到，尽管这个序列是一个堆，但是它的元素并不完全是按降序排列。这清楚地表明，尽管优先级队列是一个堆，但堆元素的顺序并不一定要和优先级队列相同。

当然，也可以用自己的比较函数来创建堆，但是必须和 push_heap() 使用相同的比较函数：

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number),greater<>());
// number : 0 4 1 7 5 2 6
number.push_back(3);
// number : 0 4 1 7 5 2 6 3
push_heap(begin(number),end(number),greater<>());
// number : 0 3 1 4 5 2 6 7

如果 push_heap() 和 make_heap() 的第 3 个参数不同，代码就无法正常执行。

删除最大元素和添加元素到堆的过程有些相似，但所做的事是相反的。首先调用 pop_heap()，然后从容器中移除最大的元素，例如：

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number));
// number : 7 5 6 0 4 2 1
pop_heap(begin(number),end(number));
// number : 6 5 2 0 4 1 7
number.pop_back();
// number : 6 5 2 0 4 1

pop_heap() 函数将第一个元素移到最后，并保证剩下的元素仍然是一个堆。然后就可以使用 vector 的成员函数 pop_back() 移除最后一个元素。如果 make_heap() 中用的是自己的比较函数，那么 pop_heap() 的第 3 个参数也需要是这个函数：

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number),greater<>());
// number : 0 4 1 7 5 2 6
pop_heap(begin(number),end(number),greater<>());
// number : 1 4 2 7 5 6 0
number.pop_back();
// number : 1 4 2 7 5 6

从注释显示的操作结果来看，显然需要为 pop_heap() 提供一个比较运算符函数。pop_heap() 函数不会交换第一个元素和最后一个元素，它会对从 begin(number) 到 end(number) - 1 这个范围内的元素重新排序，从而保持堆的顺序。为了能够正确执行这个操作，pop_heap() 必须和 make_heap() 使用相同的比较函数。

判断是否为堆的方法：

is_heap(std::begin(numbers),std::end(numbers))

如果元素段是堆，那么 is_heap() 会返回 true。这里是用默认的比较断言 less<> 来检查元素顺序。如果这里使用的是用 greater<> 创建的堆，就会产生错误的结果。为了得到正确的结果，表达式需要写为：

is_heap(std::begin(numbers),std::end(numbers),std::greater<>())

甚至可以更深入地检查元素中是否有部分元素为堆。例如

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number),greater<>());
// number : 0 4 1 7 5 2 6
pop_heap(begin(number),end(number),greater<>());
// number : 1 4 2 7 5 6 0
auto iter = is_heap_until(begin(number),end(number),greater<>());
if(iter != end(number)){
    cout<<*iter<<endl;
}
// *iter : 0

is_heap_until() 函数返回一个迭代器，指向第一个不在堆内的元素。这个代码段会输出最后一个元素的值 0 ，因为在调用 pop_heap() 后，这个元素就不在堆内了。如果整段元素都是堆，函数会返回一个结束迭代器，因此if语句可以确保我们不会解引用一个结束迭代器。如果这段元素少于两个，也会返回一个结束迭代器。这里还有另一个版本的 is_heap_until()，它有两个参数，以 less<> 作为默认断言。

STL 提供的最后一个操作是 sort_heap()，它会将元素段作为堆来排序。如果元素段不是堆，程序会在运行时崩溃。这个函数有以两个迭代器为参数的版本，迭代器指向一个假定的大顶堆(用 less<> 排列)，然后将堆中的元素排成降序。结果当然不再是大顶堆。下面是一个使用它的示例：

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number));
// number : 7 5 6 0 4 2 1
sort_heap(begin(number),end(number));
// number : 0 1 2 4 5 6 7

排序操作的结果不是一个大顶堆，而是一个小顶堆。尽管堆并不是全部有序的，但任何全部有序的序列都是堆。

第 2 个版本的 sort_heap() 有第 3 个参数，可以指定一个用来创建堆的断言。如果用断言 greater() 来创建堆，会生成一个小顶堆，对它进行排序会生成一个降序序列。排序后的序列不是小顶堆。下面的代码对此做了展示：

vector<int> number{5,0,1,7,4,2,6};
make_heap(begin(number),end(number),greater<>());
// number : 0 4 1 7 5 2 6
sort_heap(begin(number),end(number),greater<>());
// number : 7 6 5 4 2 1 0

最后一行注释中显示的那样，对小顶堆执行 sort_heap() 后，会变成一个大顶堆。

我们知道可以用定义在 algorithm 头文件中的函数模板 sort() 来对堆排序，那么为什么还需要 sort_heap() 函数？sort_heap() 函数可以使用特殊的排序算法，巧合的是它被叫作堆排序。这个算法首先会创建一个堆，然后充分利用数据的局部有序性对数据进行排序。sort_heap 认为堆总是存在的，所以它只做上面的第二步操作。充分利用堆的局部有序性可以潜在地使排序变得更快。

至此， STL 中的 priority_queue 容器，堆的使用介绍就暂告一段落了。