猫史档案馆

【C++OI基础教程】数据结构教程详解

栈和队列这种非常简单的就没必要讲了，用kitten都能很快做出来。关于栈的话，大家可以搜搜我的“kitten高阶教程”的那个。如果要了解队列，可以看看Max（就是无情的AC自动鸡）神犇的帖子。（路卡西欧的就算了，讲的并不好）

 

 

 

堆

 

定义：堆，又称优先队列，是具有堆性质的完全二叉树。

存储方式：对于属于该堆的任意一节点x，满足x的权值是以x为根的子树的权值的最大（最小）值。该堆称为大根堆（小根堆）。

 

由于堆的主要操作类似队列的最值操作，因此堆别称为优先队列(priority_queue)。

 

堆（优先队列）的声明

 

使用以下头文件

#include<queue>

 

以及加入这一行调用std名字空间

using std::priority_queue;

 

定义如下（std模板库默认为大根堆）

priority_queue<int>Q;//定义一个int类型的叫做Q的堆（优先队列）

 

下面给出一些常用函数

Q.push(a);
//将a插入堆中
x=Q.top();
//获取堆顶元素
Q.top();