深度剖析C++ STL priority_queue适配器底层的堆结构

198 阅读 0 评论 2 点赞

在《C++ STL priority_queue适配器入门》我们就曾提到优先队列的底层结构是堆，具体是二叉堆，这个二叉堆可以类比二叉树进行学习。可能有读者存疑了，本章不是在学习容器适配器吗，怎么会谈到底层结构呢，这么说优先队列底层到底是堆还是vector容器还是deque容器呢？其实，结构和容器是两个完全不同的概念，但是它们可以组合在一起！就适配容器而言，优先队列采用vector容器或deque容器做底层容器，主要是这两个容器能够动态扩容，支持随机访问和元素连续存储；就整个结构而言，堆是一种数据结构，优先队列的堆是一个二叉堆，它是通过数组来模拟二叉树的链式结构，节点i的父节点是(i-1)/2，其左子树是i*2+1，右节点是i*2+2。

二叉堆

对于二叉堆来说：

如果所有父节点都大于等于他们的子节点，那我们称该二叉堆为大顶堆，反之为小顶堆。

STL库中的<algorithm>为我们准备了配置二叉堆的相关函数：

函数	参数	功能
`std::make_heap`	`(first, last[, comp])`	将 `[first, last)` 范围内的元素构建成一个堆结构
`std::push_heap`	`(first, last[, comp])`	假设 `[first, last-1)` 已是堆，将 `last-1` 位置的元素加入到堆中并重新调整
`std::pop_heap`	`(first, last[, comp])`	将堆顶元素（`first`）与最后一个元素（`last-1`）交换，然后对 `[first, last-1)` 重新建堆
`std::sort_heap`	`(first, last[, comp])`	将一个堆序列 `[first, last)` 转换成有序序列（升序或降序，取决于堆类型）
`std::is_heap`	`(first, last[, comp])`	检查 `[first, last)` 范围内的元素是否满足堆结构，返回 `bool`
`std::is_heap_until`	`(first, last[, comp])`	查找 `[first, last)` 中满足堆结构的最大子范围，返回结束迭代器

这些配置堆的函数笔者就不过多赘述了，下面让我们通过代码来简单认识它们吧：

#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>//配置堆的函数 
using namespace std;
/*vector容器、deque容器或queue适配器都可以做堆的底层容器*/ 
/*天然的公共类*/ 
struct cmp
{
bool operator()(const int& a,const int& b)const 
{
return a>b;
}
};
void test() 
{
/*进行堆的设计*/
/*存储容器*/ 
vector<int> v{1,4,5,2,3} ;
deque<int> dq{1,4,5,2,3} ;
/*make_heap构建堆结构*/
/*大根堆*/ 
make_heap(v.begin(),v.end());
cout <<"make_heap默认大根堆：【" <<v.front() << "】\n" ;
/*小根堆*/
make_heap(dq.begin(),dq.end(),cmp());//使用到仿函数
cout <<"make_heap更改规则后实现小根堆：【"<< dq.front() << "】\n" ; 
/*push_heap添加元素后调整*/
v.push_back(6) ;
push_heap(v.begin(),v.end());//已知v是堆的情况下重新调整堆结构 
cout << "调整后保持堆结构：【"  << v[0] << "】\n";
/*pop_heap()*/
pop_heap(v.begin(),v.end()) ;//移除堆顶元素，并重新维护堆
cout << "移除堆顶元素后，并重新维护堆：【"  <<v[0] <<"】\n";
/*sort_heap*/
sort_heap(v.begin(),v.end()) ;//将堆进行排序，也可以sort(v.begin(),v.end()) 
cout << "排序后："; 
for(vector<int>::iterator it = v.begin();it!=v.end();++it) cout << *it << " ";
cout<< '\n' ;
/*is_heap*/
/*细节：默认检查大根堆，可以添加仿函数实现小根堆*/ 
cout << "现在v非堆，dq为堆，分别对其进行判断：" << "【" << is_heap(v.begin(),v.end())  << "】" << " 【" <<  is_heap(dq.begin(),dq.end(),cmp()) << "】\n"; 
/*is_heap_unitl*/
/*返回区间里指向第一个不满足堆结构的元素的迭代器*/ 
dq.push_back(6) ;
cout <<"刚插入一个元素6，由于没有push_heap()所以会返回指向6的迭代器"<<  *(is_heap_until(dq.begin(),dq.end(),cmp())-1) <<'\n' ;
}
int main() {
    test();
    return 0;
}

编译结果如下：

有关堆的函数操作