平板电视（pb_ds）详解

前言

因楼主初学平板电视，本篇文章需不定时更新修订。

简介

平板电视，也就是 pb_ds，全称是 Policy-Based Data Structures。是C++中的一个库（类似于STL），其中封装了许多高级的数据结构，例如堆，字典树，平衡树，哈希表等等。平板电视也可以用来写红黑树，AVL等高级数据结构及算法（虽然我对此一窍不通），是那些懒得写高级数据结构的dalao的福音。

另外，声明一下，平板电视应用在于_gnu_pbds的命名空间中，由于NOI在2021年才允许使用由下划线开头的函数。所以，平板电视在2021时才被CCF允许使用。

因为oiwiki在这一方面描述的非常“简陋”，于是推荐一篇来自于洛谷的博客

声明

使用平板电视之前建议先声明一下命名空间

using namespace __gnu_pbds
1

为了应用平板电视，不同的封装于平板电视里的数据结构有着不同的头文件，先给大家介绍一种简单明了的头文件

#include
1

but! DEV是不支持这个头文件的，但是洛谷等OJ（除了POJ都是支持的，八中OJ也是支持的）。

封装数据结构

堆（优先队列）

平板电视里也可以用到优先队列的。和STL里的优先队列一样，平板电视里的优先队列同样也是通过“反着来”这个定律进行排序的。

声明

因为怕平板电视会和std库里的

priority_queue<int>q;
1

发生冲突，故要变成

__gnu_pbds::priority_queue<int>q;
1

以上是大根堆，小根堆和STL里的一样

__gnu_pbds::priority_queue<int,greater<int> >pq;
1

另外，还有其他类型的堆的声明方式（可惜我全部不懂，只能展示给各位dalao们看,dalao们应该知道）

__gnu_pbds::priority_queue<int,greater<int>,binary_heap_tag>pq;//二叉堆
__gnu_pbds::priority_queue<int,greater<int>,binomial_heap_tag>pq;//二顶堆
__gnu_pbds::priority_queue<int,greater<int>,piaring_heap_tag>pq; //配对堆
__gnu_pbds::priority_queue<int,greater<int>,thin_heap_tag>pq; //斐波那契堆
1
2
3
4

参数

这个我不太懂，可以问问我们机房这方面的dalao @ybc2025-11-tangruichen(逃

我目前只知道

• 定义的时候可以不用 vector
• 参数分为三种类型：仿函数类，元素类型，堆得类型
• 堆的类型在上文声明的时候已经提到过了，不用赘述了
• 仿函数类可以使用 greater,less,同时也可以自己手写一个如下

struct node{
    bool operator()(node a,node b){
        return a.x<b.x;
    }
};
//重载，按x降序排序
1
2
3
4
5
6

常见操作

具体的操作和普通的优先队列区别不大

push()//入堆
top()//返回堆顶
size()//返回堆的大小
empty()//判断是否为空
clear()//清空
pop()//弹出堆顶元素
join(priority_queue,&other)//合并两个堆.other会被清空
split(Pred prd,priority_queue &other)//分离除两个堆
modify(point_iterator it,const key)//修改一个节点的值
1
2
3
4
5
6
7
8
9

注意，平板电视中的堆仍然后STL中的略有不同，其 push() 函数是有返回值的，返回的类型是一个迭代器，由此，我们可以知道，平板电视里的优先队列可以随时任意的修改单个元素的值。

另外，平板电视的堆也有其自己的迭代器，其声明的方式是：

__gnu_pbds::priority_queue<int>::point_iterator iter;
1

在用这个迭代器时，我们也许会用的一个修改的函数:

q.modify(it,y);//it是迭代器,y是新元素
1

平板电视里的优先队列有一个特性，当迭代器声明之前，it里的值全部都是NULL，所以，我们可以用此特性来判断一个元素在不在堆中

具体演示

众所周知，用堆的地方无处不在，今天我们就那dijkstra算法举例。

其实和普通的dijkstra堆优化没什么区别，只不过是优先队列的类型换了，思路还是那个思路。

int dis[10005];
vector<pair<int,int>>vec[10005];
//存图
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>,pairing_heap_tag>q;
//声明配对堆
__gnu_pbds::priority_queue<piar<int,int>,greater<pair<int,int>>,pairing_heap_tag>::point_iterator it[10005];
//声明配对堆的迭代器
void dijkstra(int x){
    q.clear();
	for(int i=1;i<=n;i++){
		dis[i]=0x3f3f3f3f;
	}
	dis[x]=0,it[x]=q.push({0,x});
    while(!q.empty()){
        int now=q.top().second;
        q.pop();
        for(auto e:vec[now]){
            if(dis[e.first]>dis[now]+e.second){
                dis[e.first]=dis[now]+e.second;
                if(it[e.first]!=NULL){
                    q.modify(it[e.first],{dis[e.first],e.first});
                }else{
                    it[e.first]=q.push({dis[e.first],e.first});
                }
            }
        }
    }//和普通dijkstra堆优化一样的思路
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（这代码的调试可花了我好长时间）

合并

自定义仿函数类

平衡树（tree）

哈希表（hash）

字典树（trie）

后序

未完待续……

注：本蒟蒻通过一名机房dalao的推荐来学平板电视，初学，偶有差错，麻烦指出。