数据结构第六节——堆
特殊的二叉树——堆~~~
堆：每个节点的值总是不大于或不小于其父节点的值的完全二叉树。
知识点小汇：
-
堆的根节点总是最小/最大值。
-
大根堆：父节点的值总是大于等于其两个儿子节点的值，根节点的值最大的堆。
-
小根堆：父节点的值总是小于等于其两个儿子节点的值，根节点的值最小的堆。
一、建堆的准备工作
- 一个空数组——用于储存堆中元素
- 一个变量——用于记录堆中元素数量
代码实现
const int Max = 1e5;
int l = 0;
int heap[ Max + 10 ];
另外，我们也可以用vector来储存堆
代码实现
vector<int> heap_;
int l_ = heap_.size();
对于堆这种数据结构，它也有如下一系列操作 ：
首先我们要进行一些准备工作~~~
- 定义Up（）函数
- 定义Down（）函数
代码实现
定义Up（）函数:辅助构造Insert（）函数
void Up( int k ){
//对于第k个元素（此时应该是队尾元素）
//当 k > 1（即不为根时），且其值小于（或大于）其父亲时，交换他和他父亲的值——即上跳
while ( k > 1 && heap[k] < heap[ k/2 ] ){
swap( heap[k], heap[ k/2 ] );
k /= 2; //跳完后，将k的值更新（现在他在他爹的位置上）
}
}
定义Down()函数：辅助构造删除函数
void Down( int k ){
while ( k + k <= l ){ //当左儿子存在时
//定义左、右儿子
int left = k + k;
int right = left + 1;
//判断换上来的元素需要和左儿子还是右二子换位，以小根堆为例
//右儿子存在且小于左儿子时，考虑右儿子
if ( right <= l && heap[ right ] < heap[ left ] ) left++;
//若其小于等于左儿子则考虑左儿子即可
if( heap[k] <= heap[left] ) break;
//交换k和某个儿子的位置（即下调）
swap( heap[k], heap[left] );
//交换后更新k的位置
k = left;
}
}
结束了紧张刺激的准备工作，下面就到了所谓的 “ 一系列操作 ” 环节~
代码实现
一、定义插入函数
void Insert ( int x ){
heap[++l] = x; //先将x插入堆尾
Up( l ); //再根据大小情况（视其为大/小根堆而定）逐个上跳至其对应位置
}
二、定义删除堆顶元素函数
void Pop()
{
swap( heap[1], heap[l] );//先将堆顶元素和堆尾元素交换位置
l --; //再将堆尾元素（原来的堆顶元素）删去
Down( 1 );//将换至堆顶的元素，调整至对应位置
}
三、定义删除任意元素函数——输入堆中位置，进行删除
void Delete ( int p ){
//如果是堆尾元素，直接删除即可
if ( p == l ) {
l--;
return;
}
//如果不是堆尾元素，则需要进一步考虑
//将需要删除的数记为 x，堆尾元素记为 y
int x = heap[p], y = heap[l];
//首先将其与堆尾元素交换位置
swap( heap[p] , heap[l] );
//再将队尾元素删除（即删除换过来的需要被删除的元素p)
l--;
//对于已经换位结束的堆，需要判断换上来的队尾元素需要如何调整才能保证不改变其堆的性质
//大、小根堆性不变
//依然以小根堆为例
//如果换上来一个更小的数，则考虑向上移动
if ( y < x ) Up(p);
//如果换上来一个更大的数，则考虑向下移动
else Down(p);
}
当然同其他数据结构一样，堆也有其相应的STL函数——priority_queue（优先队列）
常用功能
- empty（）判断是否为空
- size（）返回队列内元素个数—— pq.size（） = l = v.size()
- top（）访问队首元素——heap[1]
- push（）插入一个元素——插入函数
- pop（）弹出队首元素）——删除堆顶元素函数
构造大、小根堆：
- 小根堆：
priority_queue<int, vector<int>, greater<int> > pq_small; - 大根堆：
priority_queue<int, vector<int>, less<int> > pq_big_;