就是stl里的优先队列
堆是一棵完全二叉树
除了最后一层 上面所有节点都是满的 最后一层是从左到右排列
小根堆 每一个点都小于等于左右子节点的 根节点就是最小值
存储
根节点是1 x的左儿子是2x 右儿子是2x+1
1.插入一个数 heap[++size]=x; up[size];
2.求集合当中最小值 heap[1]; 根节点就是最小的
3.删除最小值 heap[1]=heap[size]; size–; down(1); 用尾节点替换最小的堆顶 向下调整
4.删除任意一个元素 heap[k]=heap[size]; size–; down(k);up(k) //不知大小关系
5.修改任意一个元素 heap[k]=x; down(x);up(x);//同理 不知大小关系直接down了在up
[堆排序] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| //思路就是将序列建成堆结构 每一次输出堆顶
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int h[N].size;
void down(int u) //往下调整 up是往上调整
{
int t=u;
if (u*2<=size && h[u*2]<h[t]) t=u*2;
if (u*2+1<=size && h[u*2+1]<h[t]) t=u*2+1; //经过操作t是u和其两个儿子里最小的
if(u!=t) //如果u不是三个节点里最小的
{
swap(h[u],h[t]);
down(t);//对交换前儿子节点的下标进行递归操作
}
}
void up(int u)
{
while(u/2 && h[u/2]>h[u] ) //由于向下取整 两个儿子除二就是父节点
{
swap(h[u],h[u/2]);
u/=2;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
size=n;
for(int i=n/2;i;i--) down(i);//建堆 二分之n是从倒数第二层开始调整每一个点 保证每一次down的时候下面的两个儿子已经是堆了
while(m--)
{
cout<<h[1];//根节点是最小的 将其输出后用尾节点替换 再将尾节点删除 递归down
h[1]=h[size];
size--;
down(1);
}
}
|
I x 插入一个数x
PM 输出当前集合中最小值
DM 删除当前集合最小值(不唯一时删除最早插入的)
D k 删除第k个插入的数
C k x 修改第k个插入的数为x
[模拟堆] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int h[N],size;
int ph[N],hp[N]; //ph[k]存第k个插入的数的下标 hp[q]存堆中下标为q的 点是第几个插入的点 ph与hp是类似于反函数的关系
//因为要准确知道第k个数 手写维护映射关系比较麻烦 直接新定义个swap
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]); //a b是第a1 b1个插入的点 将第a1 b1个插入的数的下标交换
swap(hp[a],hp[b]);
swap(h[a],h[b]); //交换值
}
void down(int u)
{
int t=u;
if (u*2<=size && h[u*2]<h[t]) t=u*2;
if (u*2+1<=size && 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(h[u],h[u/2]);
u/=2;
}
}
int main()
{
int n,m=0; // m表示第k个插入的数
cin>>n;
while(n--)
{
char op[10];
int k,x;
cin>>op;
if(!strcmp(op,"I"))
{
cin>>x;
size++;
m++;
ph[m]=size,hp[size]=m;
h[size]=x;
up(size); //插入是插到最后嘛 由下而上ip
}
else if(!strcmp(op,"PM")) cout<<h[1];
else if(!strcmp(op,"DM")) //删除堆顶
{
heap_swap(1,size);
size--;
down(1);
}
else if(!strcmp(op,"D")) //删除第k个插入的元素
{
cin>>k;
k=ph[k]; //第k个插入的数的下标
heap_swap(k,size);
size--;
down(k),up(k);
}
else //修改第k个插入的数
{
cin>>k>>x;
k=ph[k];
h[k]=x;
down(k),up(k);
}
}
return 0;
}
|
其实一般遇不到有这种映射关系的堆 只需普通up down就行了
但是这是为之后搜索内容做铺垫
