1.最小堆、最大堆
priority_queue<int,vector<int>,greater<int> > f; //最小堆(后面的数逐渐greater)
priority_queue<int,vector<int>,less<int> > f;//最大堆(后面的数逐渐less)
(1).合并果子
https://www.vijos.org/p/1097
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <stdbool.h> 6 #include <set> 7 #include <vector> 8 #include <map> 9 #include <queue> 10 #include <algorithm> 11 #include <iostream> 12 using namespace std; 13 14 priority_queue<int,vector<int>,greater<int> > f; 15 16 int main() 17 { 18 long n,i,a,x,y=0; 19 scanf("%ld",&n); 20 for (i=1;i<=n;i++) 21 { 22 scanf("%ld",&a); 23 f.push(a); 24 } 25 for (i=1;i<n;i++) 26 { 27 x=f.top(); 28 f.pop(); 29 x+=f.top(); 30 f.pop(); 31 f.push(x); 32 y+=x; 33 } 34 printf("%ld",y); 35 return 0; 36 }
2.自定义
测试：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cmath> 5 #include <stdbool.h> 6 #include <set> 7 #include <vector> 8 #include <map> 9 #include <queue> 10 #include <stack> 11 #include <algorithm> 12 #include <iostream> 13 using namespace std; 14 #define maxn 100000+5 15 #define inf 100000+5 16 17 long f[maxn],pos[maxn]; 18 19 //×î´ó¶Ñ 20 struct cmp1 21 { 22 bool operator() (long a,long b) 23 { 24 return f[a]<f[b]; 25 } 26 }; 27 28 //×îС¶Ñ 29 struct cmp2 30 { 31 bool operator() (long a,long b) 32 { 33 return f[a]>f[b]; 34 } 35 }; 36 37 //Ç°1/2:a ºó1/2£ºb 38 priority_queue<int,vector<int>,cmp1 > a; 39 priority_queue<int,vector<int>,cmp2 > b; 40 41 int main() 42 { 43 long n,d,i; 44 scanf("%ld",&n); 45 for (i=1;i<=n;i++) 46 { 47 scanf("%ld",&f[i]); 48 // a.push(i); 49 b.push(i); 50 } 51 // while (!a.empty()) 52 while (!b.empty()) 53 { 54 // printf("%ld ",f[a.top()]); 55 // a.pop(); 56 printf("%ld ",f[b.top()]); 57 b.pop(); 58 } 59 return 0; 60 } 61 /* 62 5 63 2 4 5 1 3 64 */
最短路用堆实现，时间复杂度O(nlogn)，其实可以用下面的3方法实现，使堆中的数据永远小于等于n个，但是编写比较复杂
两道例题：
http://www.cnblogs.com/cmyg/p/8727643.html
3.对于需要修改、删除堆里的数据，需要自行写堆(优先队列) 参见算法导论
以下是使用优先队列修改、删除堆里的数据，发生错误的案例(代入数据)：
1 //要删除指定值的话只能自己写一个优先队列 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <stdbool.h> 7 #include <set> 8 #include <vector> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <algorithm> 13 #include <iostream> 14 using namespace std; 15 #define maxn 100000+5 16 #define inf 100000+5 17 18 long f[maxn],pos[maxn]; 19 20 //最大堆 21 struct cmp1 22 { 23 bool operator() (long a,long b) 24 { 25 return f[a]<f[b]; 26 } 27 }; 28 29 //最小堆 30 struct cmp2 31 { 32 bool operator() (long a,long b) 33 { 34 return f[a]>f[b]; 35 } 36 }; 37 38 //从小到大排序 39 //前(n+1)/2个数：a(最大堆) 40 //后n/2个数：b(最小堆) 41 //中位数永远是a的最大值 42 //增添和删除：也许需要a的最大值移向b或b的最小值移向a 43 priority_queue<int,vector<int>,cmp1 > a; 44 priority_queue<int,vector<int>,cmp2 > b; 45 46 void change() 47 { 48 long d; 49 if (a.size()<b.size()) 50 { 51 d=b.top(); 52 b.pop(); 53 a.push(d); 54 pos[d]=0; 55 } 56 else if (a.size()>b.size()+1) 57 { 58 d=a.top(); 59 a.pop(); 60 b.push(d); 61 pos[d]=1; 62 } 63 } 64 65 int main() 66 { 67 long n,g; 68 char s[20]; 69 scanf("%ld",&n); 70 while (n) 71 { 72 n--; 73 scanf("%s",s); 74 if (strcmp(s,"Pop")==0) 75 { 76 if (g==0) 77 { 78 printf("Invalid "); 79 continue; 80 } 81 printf("%ld ",f[g]); 82 if (pos[g]==0) 83 { 84 f[g]+=inf; 85 86 printf("--%ld ",a.top()); 87 88 a.pop(); 89 90 printf("--%ld ",a.top()); 91 //这里错了 92 } 93 else 94 { 95 f[g]-=inf; 96 b.pop(); 97 } 98 g--; 99 change(); 100 } 101 else if (strcmp(s,"Push")==0) 102 { 103 g++; 104 scanf("%ld",&f[g]); 105 if (a.empty() || f[g]<=f[a.top()]) 106 { 107 a.push(g); 108 pos[g]=0; 109 } 110 else 111 { 112 b.push(g); 113 pos[g]=1; 114 } 115 change(); 116 } 117 else 118 { 119 if (g==0) 120 printf("Invalid "); 121 else 122 printf("%ld ",f[a.top()]); 123 } 124 } 125 return 0; 126 } 127 /* 128 100 129 Push 1 130 PeekMedian 131 Push 2 132 PeekMedian 133 Push 3 134 PeekMedian 135 Push 4 136 PeekMedian 137 Push 5 138 PeekMedian 139 Pop 140 PeekMedian 141 Pop 142 PeekMedian 143 Pop 144 PeekMedian 145 Pop 146 PeekMedian 147 Pop 148 PeekMedian 149 Pop 150 151 152 100 153 Push 5 154 PeekMedian 155 Push 4 156 PeekMedian 157 Push 3 158 PeekMedian 159 Push 2 160 PeekMedian 161 Push 1 162 PeekMedian 163 Pop 164 PeekMedian 165 Pop 166 PeekMedian 167 Pop 168 PeekMedian 169 Pop 170 PeekMedian 171 Pop 172 PeekMedian 173 Pop 174 175 176 177 */
3.1 求第k大，k的值每次最多变化为1
求中位数
https://www.patest.cn/contests/gplt/L3-002
Solution：
分成两个堆，
对数从小到大排序
前(n+1)/2个数：a(最大堆)
后n/2个数：b(最小堆)
中位数永远是a的最大值
增添和删除：也许需要a的最大值移向b或b的最小值移向a
注意pos和input数组，这个是用于定位的，从而可以修改数据，删除数据
1 //还可以求第k大(k值固定) 2 3 //要删除指定值的话只能自己写一个优先队列 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cmath> 8 #include <stdbool.h> 9 #include <set> 10 #include <vector> 11 #include <map> 12 #include <queue> 13 #include <stack> 14 #include <algorithm> 15 #include <iostream> 16 using namespace std; 17 #define maxn 100000+5 18 #define inf 100000+5 19 20 struct node 21 { 22 long d,g; 23 }; 24 25 long f[maxn],treenum[maxn]; 26 //posa[i],posb[i]:a/b中第i个点在输入中的位置 27 //input[i]:输入中第i个点在树的位置(pos标记是在哪棵树) 28 long a[maxn],b[maxn],posa[maxn],posb[maxn],input[maxn]; 29 30 //最大堆 31 struct cmp1 32 { 33 bool operator() (long a,long b) 34 { 35 return f[a]<f[b]; 36 } 37 }; 38 39 //最小堆 40 struct cmp2 41 { 42 bool operator() (long a,long b) 43 { 44 return f[a]>f[b]; 45 } 46 }; 47 48 //从小到大排序 49 //前(n+1)/2个数：a(最大堆) 50 //后n/2个数：b(最小堆) 51 //中位数永远是a的最大值 52 //增添和删除：也许需要a的最大值移向b或b的最小值移向a 53 //priority_queue<int,vector<int>,cmp1 > a; 54 //priority_queue<int,vector<int>,cmp2 > b; 55 56 void up_min(long t[],long pos[],long input[],long i) 57 { 58 long j,temp; 59 while (i>1) 60 { 61 j=i>>1; 62 //j<i 63 if (t[j]>t[i]) 64 { 65 temp=t[i]; 66 t[i]=t[j]; 67 t[j]=temp; 68 69 temp=pos[i]; 70 pos[i]=pos[j]; 71 pos[j]=temp; 72 73 input[pos[i]]=i; 74 input[pos[j]]=j; 75 } 76 else 77 break; 78 i=j; 79 } 80 } 81 82 void down_min(long t[],long pos[],long input[],long i) 83 { 84 long j,temp; 85 while (( i<<1)<=t[0]) 86 { 87 j=i<<1; 88 if (j!=t[0] && t[j+1]<t[j]) 89 j=j|1; 90 //i<j 91 if (t[i]>t[j]) 92 { 93 temp=t[i]; 94 t[i]=t[j]; 95 t[j]=temp; 96 97 temp=pos[i]; 98 pos[i]=pos[j]; 99 pos[j]=temp; 100 101 input[pos[i]]=i; 102 input[pos[j]]=j; 103 } 104 else 105 break; 106 i=j; 107 } 108 } 109 110 void push_min(long t[],long pos[],long input[],struct node p) 111 { 112 t[0]++; 113 t[t[0]]=p.d; 114 pos[t[0]]=p.g; 115 input[p.g]=t[0]; 116 up_min(t,pos,input,t[0]); 117 } 118 119 void pop_min(long t[],long pos[],long input[]) 120 { 121 t[1]=t[t[0]]; 122 pos[1]=pos[t[0]]; 123 input[pos[1]]=1; 124 t[0]--; 125 down_min(t,pos,input,1); 126 } 127 128 void minus_min(long t[],long pos[],long input[],long w,long d) 129 { 130 t[w]-=d; 131 up_min(t,pos,input,w); 132 } 133 134 void plus_min(long t[],long pos[],long input[],long w,long d) 135 { 136 t[w]+=d; 137 down_min(t,pos,input,w); 138 } 139 140 141 void up_max(long t[],long pos[],long input[],long i) 142 { 143 long j,temp; 144 while (i>1) 145 { 146 j=i>>1; 147 //j<i 148 if (t[j]<t[i]) 149 { 150 temp=t[i]; 151 t[i]=t[j]; 152 t[j]=temp; 153 154 temp=pos[i]; 155 pos[i]=pos[j]; 156 pos[j]=temp; 157 158 input[pos[i]]=i; 159 input[pos[j]]=j; 160 } 161 else 162 break; 163 i=j; 164 } 165 } 166 167 void down_max(long t[],long pos[],long input[],long i) 168 { 169 long j,temp; 170 while ((i<<1)<=t[0]) 171 { 172 j=i<<1; 173 if (j!=t[0] && t[j+1]>t[j]) 174 j=j|1; 175 //i<j 176 if (t[i]<t[j]) 177 { 178 temp=t[i]; 179 t[i]=t[j]; 180 t[j]=temp; 181 182 temp=pos[i]; 183 pos[i]=pos[j]; 184 pos[j]=temp; 185 186 input[pos[i]]=i; 187 input[pos[j]]=j; 188 } 189 else 190 break; 191 i=j; 192 } 193 } 194 195 void push_max(long t[],long pos[],long input[],struct node p) 196 { 197 long i,j,temp; 198 t[0]++; 199 t[t[0]]=p.d; 200 pos[t[0]]=p.g; 201 input[p.g]=t[0]; 202 up_max(t,pos,input,t[0]); 203 } 204 205 void pop_max(long t[],long pos[],long input[]) 206 { 207 t[1]=t[t[0]]; 208 pos[1]=pos[t[0]]; 209 input[pos[1]]=1; 210 t[0]--; 211 down_max(t,pos,input,1); 212 } 213 214 void plus_max(long t[],long pos[],long input[],long w,long d) 215 { 216 t[w]+=d; 217 up_max(t,pos,input,w); 218 } 219 220 void minus_max(long t[],long pos[],long input[],long w,long d) 221 { 222 t[w]-=d; 223 down_max(t,pos,input,w); 224 } 225 226 long size(long t[]) 227 { 228 return t[0]; 229 } 230 231 struct node top(long t[],long pos[]) 232 { 233 struct node p; 234 p.d=t[1]; 235 p.g=pos[1]; 236 return p; 237 } 238 239 bool empty(long t[]) 240 { 241 if (t[0]==0) 242 return true; 243 else 244 return false; 245 } 246 247 void change() 248 { 249 struct node cond; 250 long d; 251 if (size(a)<size(b)) 252 // if (a.size()<b.size()) 253 { 254 cond=top(b,posb); 255 pop_min(b,posb,input); 256 push_max(a,posa,input,cond); 257 // d=b.top(); 258 // b.pop(); 259 // a.push(d); 260 treenum[cond.g]=0; 261 } 262 else if (size(a)>size(b)+1) 263 // else if (a.size()>b.size()+1) 264 { 265 cond=top(a,posa); 266 pop_max(a,posa,input); 267 push_min(b,posb,input,cond); 268 // d=a.top(); 269 // a.pop(); 270 // b.push(d); 271 treenum[cond.g]=1; 272 } 273 } 274 275 int main() 276 { 277 struct node cond; 278 long n,g; 279 char s[20]; 280 a[0]=0; b[0]=0; 281 scanf("%ld",&n); 282 while (n) 283 { 284 n--; 285 scanf("%s",s); 286 if (strcmp(s,"Pop")==0) 287 { 288 if (g==0) 289 { 290 printf("Invalid "); 291 continue; 292 } 293 printf("%ld ",f[g]); 294 if (treenum[g]==0) 295 { 296 // f[g]+=inf; 297 // a.pop(); 298 plus_max(a,posa,input,input[g],inf); 299 pop_max(a,posa,input); 300 } 301 else 302 { 303 // f[g]-=inf; 304 // b.pop(); 305 minus_min(b,posb,input,input[g],inf); 306 pop_min(b,posb,input); 307 } 308 g--; 309 change(); 310 } 311 else if (strcmp(s,"Push")==0) 312 { 313 g++; 314 scanf("%ld",&f[g]); 315 // if (a.empty() || f[g]<=f[a.top()]) 316 if (empty(a) || f[g]<=top(a,posa).d) 317 { 318 cond.d=f[g]; 319 cond.g=g; 320 // a.push(g); 321 push_max(a,posa,input,cond); 322 treenum[g]=0; 323 } 324 else 325 { 326 cond.d=f[g]; 327 cond.g=g; 328 // b.push(g); 329 push_min(b,posb,input,cond); 330 treenum[g]=1; 331 } 332 change(); 333 } 334 else 335 { 336 if (g==0) 337 printf("Invalid "); 338 else 339 // printf("%ld ",f[a.top()]); 340 printf("%ld ",top(a,posa).d); 341 } 342 } 343 return 0; 344 } 345 /* 346 100 347 Push 1 348 PeekMedian 349 Push 2 350 PeekMedian 351 Push 3 352 PeekMedian 353 Push 4 354 PeekMedian 355 Push 5 356 PeekMedian 357 Pop 358 PeekMedian 359 Pop 360 PeekMedian 361 Pop 362 PeekMedian 363 Pop 364 PeekMedian 365 Pop 366 PeekMedian 367 Pop 368 369 370 100 371 Push 5 372 PeekMedian 373 Push 4 374 PeekMedian 375 Push 3 376 PeekMedian 377 Push 2 378 PeekMedian 379 Push 1 380 PeekMedian 381 Pop 382 PeekMedian 383 Pop 384 PeekMedian 385 Pop 386 PeekMedian 387 Pop 388 PeekMedian 389 Pop 390 PeekMedian 391 Pop 392 393 */
3.2 求第k大的数(k永远不变)
前k大的数放入最小堆a，其它的数放入最大堆b
添加数据：数据放入堆a，若堆a的大小大于k，则取最小的数放入堆b
修改数据：修改后根据情况是否把一个数从a移至b或从b移至a