堆的结构实际上是一棵完全二叉树,堆可以分为大根堆和小根堆
大根堆:
小根堆:
堆的储存:
若节点小标为i,则左子节点下标为2i+1,右子节点下标为2i+2。
//down模板:
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],siz;
int n,m;
void down(int x)
{
? ? int t=x;
? ? if(2*x<=siz && h[2*x]<h[t]) t=2*x;
? ? if(2*x+1<=siz && h[2*x+1]<h[t]) t=2*x+1;
? ? if(x!=t)
? ? {
? ? ? ? swap(h[x],h[t]);
? ? ? ? down(t);
? ? }
}
//up模板:
void up(int x)
{
? ? while(x/2 &&h[x]<h[x/2])
? ? {
? ? ? ? headswap(x/2,x);
? ? ? ? x/=2;
? ? }
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, less<int> >q;
int main(){
q.push(1);
q.push(2);
cout<<q.top();
return 0;
}
或:
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int>q;
int main(){
q.push(1);
q.push(2);
cout<<q.top();
return 0;
}
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> >q;
int main(){
q.push(1);
q.push(2);
cout<<q.top();
return 0;
}
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
int h[N];//堆
int ph[N], hp[N];
int siz;
void heap_swap(int a,int b) {
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u) {
int t = u;
if (u * 2 <= siz && h[u * 2] < h[t]) {
t = u * 2;//比左儿子
}
if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) {
t = u * 2 + 1;//比右儿子
}
if (u != t) {
heap_swap(u, t);
down(t);
}
}
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
heap_swap(u / 2, u);
u /= 2;
}
}
int main () {
int n, m = 0;
scanf("%d", &n);
while (n --) {
char op[10];
int k, x;
scanf("%s", op);
if (!strcmp(op,"I")) {
scanf("%d", &x);
siz++;
m++;
ph[m] = siz, hp[siz] = m;
h[siz] = x;
up(siz);
}
else if (!strcmp(op,"PM")) {
printf("%d\n", h[1]);
}
else if (!strcmp(op,"DM")) {
heap_swap(1, siz);
siz--;
down(1);
}
else if (!strcmp(op,"D")) {
scanf("%d", &k);
k = ph[k];
heap_swap(k, siz);
siz--;
down(k), up(k);
}
else {
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}