蓝桥杯备考：堆和priority queue（优先级队列）
堆的定义
heap堆是一种特殊的完全二叉树，对于树中的每个结点，如果该结点的权值大于等于孩子结点的权值，就称它为大根堆，小于等于就叫小根堆，如果是大根堆，每个子树也是符合大根堆的特征的，如果是小根堆，每课子树符合小根堆特征
堆的存储
顺序存储，按照层序遍历编号依次存放在数组里面，变量n负责标记元素个数，存储固然简单，但是我们的 题目一般不会那么好心直接给一个标准的堆，一般只是随便给我们一组数，这组数还原出来并不一定是堆结构，我们可以用数组存下来这组数，然后把数组调整称堆，也可以依次把这些数插入到堆里面
向上调整算法
向上调整，当我们插入一个数的时候，我们需要进行向上调整
算法原理（大根堆，小根堆同理）：如果插入的数权值小于等于父亲结点，那我们不变，如果插入的数是大于父亲结点的，我们就要让它和父亲结点换位置
不断重复这个操作，直到此数变成根结点或者权值小于等于父亲结点的时候为止
比如我们尝试调整一下这棵树
void up(int child)
{
int parent = child / 2;
while (child != 1 && heap[parent] < heap[child])
{
swap(heap[parent], heap[child]);
child = parent;
parent = child / 2;
}
}向下调整算法
当我们需要删除一个结点的时候，我们只能删除堆顶的元素，这时候，我们交换堆底和堆顶元素，然后对交换上来的堆顶进行向下调整算法，如果新的堆顶的两个孩子都小于等于它，那么就不用操作，因为我的其他子树都维持着大根堆的特征，如果堆顶元素的两个孩子的较大结点大于我们的堆顶元素，此时我们就要让他和最大的孩子交换，重复此操作，直到换到叶子结点或者该结点大于等于左右孩子为止
void down(int parent)
{
int child = parent * 2;
if (heap[child + 1] > heap[child]) child = child + 1;
while (child <= n && heap[parent] < heap[child])
{
swap(heap[parent], heap[child]);
parent = child;
child = parent * 2;
}
}由于我们的向上调整算法和向下调整算法最坏的情况都是执行二叉树的深度次，又因为二叉树的深度是log（n+1) 所以我们的向上调整算法和向下调整算法就是O（log N）
堆数据结构的创建
创建
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int heap[N], n;插入
插入的时候我们就放在n下标的下一个位置，然后把新的n下标传进去进行向上调整即可
代码；
void push(int x)
{
heap[++n] = x;
up(n);
}删除
删除的时候我们要先交换堆顶和堆底元素，然后删除堆底元素n--，
然后对堆顶元素进行向下调整
void pop()
{
swap(heap[n], heap[1]);
n--;
down(1);
}
查询堆顶元素
int top()
{
return heap[1];
}时间复杂度是O（1）
查询有效元素个数
int size()
{
return n;
}
进行测试，把这个数组插入到堆里面，键堆，依次取出堆顶元素，就是个降序的过程
总代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int heap[N], n;
void up(int child)
{
int parent = child / 2;
while (child != 1 && heap[parent] < heap[child])
{
swap(heap[parent], heap[child]);
child = parent;
parent = child / 2;
}
}
void down(int parent)
{
int child = parent * 2;
if (heap[child + 1] > heap[child]) child = child + 1;
while (child <= n && heap[parent] < heap[child])
{
swap(heap[parent], heap[child]);
parent = child;
child = parent * 2;
}
}
void push(int x)
{
heap[++n] = x;
up(n);
}
void pop()
{
swap(heap[n], heap[1]);
n--;
down(1);
}
int top()
{
return heap[1];
}
int size()
{
return n;
}
int main()
{
int a[10] = { 1, 41, 23, 10, 11, 2, -1, 99, 14, 0 };
for (int i = 0; i < 10; i++)
{
push(a[i]);
}
while (size())
{
cout << top() << " ";
pop();
}
return 0;
}priority queue优先级队列的用法（初阶，进阶）
在我们的stl中，有一个现成的堆的数据结构，叫做优先级队列，有了它，我们就不用再自己手写一个堆的数据结构了
堆可以存储内置类型比如说int
堆也可以存储字符串类型
堆也可以存储自定义类型比如结构体
每一种存储方式都对应一种写法
我们先来介绍普通的存储内置类型的优先级队列
#include <iostream>
#include <queue>
using namespace std;
int a[10] = { 1, 41, 23, 10, 11, 2, -1, 99, 14, 0 };
int main()
{
priority_queue <int> heap;//这种简单的写法默认就是大根堆
for (int i = 0; i < 10; i++)
{
heap.push(a[i]);
}
while (heap.size())
{
cout << heap.top() << " ";
heap.pop();
}
return 0;
}首先是这种简单的写法，这种简单的写法默认就是大根堆
如果你想实现正经八本的一个堆的话，我们有一个模式
priority_queue<数据类型，数据实现方式，比较方式（判断大/小根堆）>
priority_queue<int, vector<int>, less<int>> q1;//大根堆
priority_queue<int, vector<int>, greater<int>> q2;//小根堆
这个需要我们特殊的记一下，大根堆用less(当第一个数小于第二个数是返回true，相当于我们sort里的比较函数一样），小根堆用greater
测试结果
测试代码
#include <iostream>
#include <queue>
using namespace std;
int a[10] = { 1, 41, 23, 10, 11, 2, -1, 99, 14, 0 };
void test()
{
priority_queue<int, vector<int>, less<int>> q1;//大根堆
priority_queue<int, vector<int>, greater<int>> q2;//小根堆
for (int i = 0; i < 10; i++)
{
q1.push(a[i]);
q2.push(a[i]);
}
while (q1.size())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
while (q2.size())
{
cout << q2.top() << " ";
q2.pop();
}
cout << endl;
}
int main()
{
priority_queue <int> heap;//这种简单的写法默认就是大根堆
/*for (int i = 0; i < 10; i++)
{
heap.push(a[i]);
}
while (heap.size())
{
cout << heap.top() << " ";
heap.pop();
}*/
test();
return 0;
}如果我们要存double和long long 只要把int改一下就行了
接下来我们来说一下结构体类型怎么建堆
如果想实现结构体类型的建堆，我们只需要在结构体内部重载小于号，如果返回b<x.b的话，就是大根堆，如果返回b>x,b的话就是小根堆
struct node {
int x, y, z;
bool operator < (const node& e)const
{
return y < e.y;//大根堆
}
};
void test2()
{
priority_queue <node> heap5;
for (int i = 1; i <= 5; i++)
{
heap5.push({ i + 5,i + 1,i + 2 });
}
while (heap5.size())
{
node t = heap5.top(); heap5.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
}
可以看到这就是大根堆
把重载的返回值改成大于就变成小根堆了，我们就不再放代码了，只要改一个符号就行
堆和priority优先级队列的算法题
1.模板题
这是一道模板题，我们先用自己手写的堆实现一下
#include <iostream>
using namespace std;
const int N = 1e6+10;
int heap[N],n;
void up(int child)
{
int parent = child/2;
while(parent >=1 && heap[parent]>heap[child])
{
swap(heap[parent],heap[child]);
child = parent;
parent = child/2;
}
}
void down(int parent)
{
int child = parent * 2;
while(child <= n)
{
if(child + 1 <= n && heap[child+1] < heap[child])
++child;
if(heap[parent] < heap[child]) return;
swap(heap[parent],heap[child]);
parent = child;
child = parent*2;
}
}
void push(int x)
{
heap[++n] = x;
up(n);
}
void pop()
{
swap(heap[1],heap[n]);n--;
down(1);
}
int main()
{
int T;cin >> T;
while(T--)
{
int op;
cin >> op;
if(op == 1)
{
int t;
cin >> t;
push(t);
}
else if(op == 2)
{
cout << heap[1] << endl;
}
else
{
pop();
}
}
return 0;
}接着用我们stl的优先级队列来实现一下
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>> heap1;
int main()
{
int n;
cin >> n;
while(n--)
{
int op;cin >> op;
if(op == 1)
{
int x;
cin >> x;
heap1.push(x);
}
else if(op == 2)
cout << heap1.top() << endl;
else
heap1.pop();
}
return 0;
}2.第k小(topk问题）
我们要维护这个优先级队列，让优先级队列里只有k个元素，然后堆顶就是我们的第k小，比如1，2，3 3就是第三小，如果要找第k小的话，实际上就是k个元素的时候的最大的值，也就是k个元素的时候的堆顶，比如1 2 3 3就是第k小，如果你插入4 5 6 1 2 3 4 5 6 最小的还是3，所以我们依次删除堆顶，留下 1 2 3 3 当堆顶的时候就是第三小 再比如 1 2 5 插入了3 那 我们删除最大的堆顶 留下 1 2 3 3也就是第三小了
#include <iostream>
#include <queue>
using namespace std;
priority_queue <int> heap1;
const int N = 2e5+10;
int a[N];
int main()
{
int n,m,k;
cin >> n >> m >> k;
for(int i = 0;i<n;i++)
{
cin >> a[i];
heap1.push(a[i]);
}
while(heap1.size() > k)
{
int t = heap1.top();heap1.pop();
}
while(m--)
{
int op;
cin >> op;
if(op == 1)
{
int x;cin >> x;
heap1.push(x);
while(heap1.size() > k)
{
heap1.pop();
}
}
if(op == 2)
{
if(heap1.size() < k)
cout << -1 << endl;
else
cout << heap1.top() << endl;
}
}
}3.除2！
如果遇到求和，我们一定要记得考虑用long long
#include <iostream> #include <queue> using namespace std; typedef long long ll; int n,k; ll sum; priority_queue <int> heap; int main() { cin >> n >> k; for(int i = 1;i<=n;i++) { int x;cin >> x; sum+=x; if(x%2 == 0) { heap.push(x); } } while(heap.size() && k--) { int t = heap.top()/2; heap.pop(); sum-=t; if(t%2 == 0) { heap.push(t); } } cout << sum << endl; return 0; }
4.最小函数值（结构体堆+单调性）
这道题我们要用构造一个结构体元素的堆，根据单调性，我们不需要一次性把所有的函数式前m个元素算出来，我们只需要先把代入值为1的值算出来，push成一个堆，然后把堆顶打印出来，把这个堆顶元素的代入值变为2再push进去，接下来再打印下一个堆顶即可
所以我们结构体要存下函数值（建堆的条件）还要存第几个函数表达式，并存下代入值x
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4+10;
int a[N],b[N],c[N];
int n,m;
struct node
{
int f;
int num;
int x;
bool operator <(const node& y) const
{
return f > y.f;//前一个元素大于后一个元素
}
};
int calc(int i,int x)
{
return a[i]*x*x + b[i]*x +c[i];
}
priority_queue <node> q;
int main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
cin >> a[i] >> b[i] >> c[i];
}
//先把代入值为1的元素push进去，然后依次出堆顶
//每次出堆顶都代入这个表达式代入的下一个值
//这个循环一共循环m次
for(int i = 1;i<=n;i++)
{
q.push({calc(i,1),i,1});
}
while(q.size() && m--)
{
node t = q.top();
q.pop();
cout << t.f << " ";
int x1 = t.x+1; int num1 = t.num;
q.push({calc(num1,x1),num1,x1});
}
return 0;
}5.序列合并（结构体堆+单调性）
这道题和上一道题非常的类似
我们这么想，先让第一个序列里最小的值和第二个序列分别相加，push进入小根堆，删除堆顶再push进第一个序列第二个小的值和第二个序列那个值相加的值，直到打印完前n个值
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
typedef long long ll;
struct node{
ll sum;
int i;
int j;
bool operator <(const node& n) const
{
return sum > n.sum;
}
};
priority_queue <node> heap;
int main()
{
int n; cin >> n;
for(int i = 1;i<=n;i++) cin >> a[i];
for(int i = 1;i<=n;i++) cin >> b[i];
for(int i = 1;i<=n;i++)
{
heap.push({a[i]+b[1],i,1});
}
for(int i = 1;i<=n;i++)
{
node t = heap.top(); heap.pop();
ll sum1 = t.sum,i1 = t.i,j1=t.j;
cout << sum1 << " ";
heap.push({a[i1]+b[j1+1],i1,j1+1});
}
return 0;
}