介绍
二叉堆是一种基础数据结构，主要应用于求出一组数据中的最大最小值。C++ 的STL中的优先队列就是使用二叉堆。
堆的性质 :
1 . 堆是一颗完全二叉树 ;
2 . 堆分为大根堆 和 小根堆(这里不讨论那些更高级的如:二叉堆，二叉堆，左偏树等等)
3 . 大根堆满足每个节点的键值都小于等于其父亲键值 ;
4 . 小根堆满足每个结点的键值都大于等于其父亲键值 ;
5 .（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
6 . 大根堆和小根堆作用相反 ;
堆的操作 :
1 . 插入
堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就丢在那里了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了 ;
示例 :
例如下图要插入一个0 :
First :
先将该元素插入末尾 :
Second :
与5比较，5>0，那么交换 :
Third :
再与2换 :
fourth :
再与1交换，变成小根堆,插入结束 :
code :
typedef long long LL ;
const int N = 1e6 + 10 ;
void swap(int &x ,int &y){int t=x;x=y;y=t;}
int heap[N] ;
int sz ;// 堆的大小
// 小根堆的插入
void push(int x){
heap[++sz] = x ;
int tmp = sz ;
while(tmp){//还没到根节点,继续交换
LL nxt = tmp >> 1 ; // 找到父节点下标
if(heap[nxt]>heap[tmp]) swap(heap[nxt],heap[tmp]);//父亲比它大，那么交换
else break ;
tmp = nxt ; // 交换下标
}
return ;
} 2 . 删除
示例 :
如果要将0删掉 :
First :
在孩子结点中找到一个较小的值进行交换 : (这里和1交换)
Second :
再与2交换 :
third :
再与5交换 :
fourth :
最后删掉即可 :
在代码实现中是直接把堆顶和堆底交换一下，然后把交换后的堆顶不断与它的子节点交换，直到这个堆重新符合堆性质 :
code :
void pop(){ // 删除堆顶
swap(heap[sz],heap[1]) ;
sz-- ;
int now = 1 ;
while((now<<1) <= sz){ // 对新栈顶进行向下的交换操作
int nxt = now << 1 ; // 找到左孩子结点下标
if(nxt+1<=sz&&heap[nxt+1]<heap[nxt]) nxt ++ ;// 找出与那个孩子交换
if(heap[nxt]<heap[now]) swap(heap[now],heap[nxt]);
else break ;
now = nxt ; // 继续下一层
}
}手写堆支持删除任意元素 ， 但是STL中的priority_queue只支持删除堆顶 ;
3 . 查询 :
直接返回堆顶（获取最大/最小值）即可 ;
堆的STL实现 :
首先需要引入头文件 :
#include<queue>然后定义priority :
priority_queue<int> q;//这是一个大根堆q
priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q优先队列的操作 :
q.top()//取得堆顶元素，并不会弹出
q.pop()//弹出堆顶元素
q.push()//往堆里面插入一个元素
q.empty()//查询堆是否为空，为空则返回1否则返回0
q.size()//查询堆内元素数量4 . 堆的复杂度
因为堆是一棵完全二叉树，所以对于一个节点数为n的堆，它的高度不会超过log2n
所以对于插入，删除操作复杂度为O(log2n)
查询堆顶操作的复杂度为O(1)
5 . 例题 :
https://www.luogu.com.cn/problem/P3378
黑匣子 - 洛谷
[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷
中位数 - 洛谷
[USACO09OPEN] Work Scheduling G - 洛谷
以【模板】堆 - 洛谷 为例 :
手写堆 :
#include<bits/stdc++.h>
using namespace std;
typedef long long LL ;
const int N = 1e6 + 10 ;
void swap(int &x ,int &y){int t=x;x=y;y=t;}
int heap[N] ;
int sz ;// 堆的大小
// 小根堆的插入
void push(int x){
heap[++sz] = x ;
int tmp = sz ;
while(tmp){//还没到根节点,继续交换
LL nxt = tmp >> 1 ; // 找到父节点下标
if(heap[nxt]>heap[tmp]) swap(heap[nxt],heap[tmp]);//父亲比它大，那么交换
else break ;
tmp = nxt ; // 交换下标
}
return ;
}
void pop(){ // 删除堆顶
swap(heap[sz],heap[1]) ;
sz-- ;
int now = 1 ;
while((now<<1) <= sz){ // 对新栈顶进行向下的交换操作
int nxt = now << 1 ; // 找到左孩子结点下标
if(nxt+1<=sz&&heap[nxt+1]<heap[nxt]) nxt ++ ;// 找出与那个孩子交换
if(heap[nxt]<heap[now]) swap(heap[now],heap[nxt]);
else break ;
now = nxt ; // 继续下一层
}
}
int main(){
int n ; cin >> n ;
while(n--){
int op ; cin >> op ;
if(op==1){
int x ; cin >> x ;
push(x);
}else if(op==2){
cout << heap[1] << endl ;
}else{
pop();
}
}
}
使用STL :
#include<bits/stdc++.h>
using namespace std;
int main(){
int n ; cin >> n ;
priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
while(n--){
int op ; cin >> op ;
if(op==1){
int x ; cin >> x ;
q.push(x);
}else if(op==2){
cout << q.top() << endl ;
}else{
q.pop();
}
}
}
