Bài toán
Xây dựng Min-max heap (hay còn gọi là priority queue hai đầu)
Cho một hàng đợi, có các thao tác : thêm một số vào hàng đợi (push), lấy và in ra số bé nhất (pop_front), lấy và in ra số lớn nhất (pop_back). Sau khi pop_front, pop_back, các phần tử được pop bị loại khỏi hàng đợi.
Độ phức tạp
chèn : O(logn)
xóa : O(logn)
đọc số lớn nhất : O(1)
đọc số bé nhất : O(1)
bộ nhớ : O(n) với n là chiều dài lớn nhất của hàng đợi
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
inline int level(int u){
for (int i=1; u&u+1; i+=i) u|=(u>>i);
return __builtin_popcount(u);
}
struct min_max_heap {
ii T[1230997];
int n;
bool adjacent_exchange(int u, int v){
if (T[u]<T[v] xor level(u)&1) swap(T[u], T[v]);
else return false;
return true;
}
bool discrete_exchange(int u, int v){
if (T[u]>T[v] xor level(u)&1) swap(T[u], T[v]);
else return false;
return true;
}
bool exchange(int u, int v){
if (u<1 || u>n || v<1 || v>n || T[u]==T[v]) return false;
int x = level(u), y = level(v);
if (abs(x-y)>2 || x==y) { printf("Fatal\n"); return false; }
if (x&1 xor y&1) return adjacent_exchange(u, v);
else return discrete_exchange(u, v);
}
int potential(int u){
int v, r=0;
for (v=u*4; v<=u*4+3 && v<=n; v++)
if ((T[v]>=T[r] xor level(u)&1) || r==0) r=v;
for (v=u*2; v<=u*2+1 && v<=n; v++) // Very important
if ((T[v]>=T[r] xor level(u)&1) || r==0) r=v;
return r;
}
void push(ii x){
int u = ++n;
T[u] = x;
if (exchange(u, u/2)) u=u/2;
while (exchange(u, u/4)) u=u/4;
}
void pop(int u){
if (u==0 || n==0) return;
T[u]=T[n--];
int v = potential(u);
while (exchange(v, u)) {
exchange(v, v/2); // Very important
u=v; v=potential(u);
}
exchange(u*2, u);
exchange(u*2+1, u);
}
int i_back(){
int r=0;
for (int i=1; i<=n && i<=3; i++)
if (T[i]>T[r] || r==0) r=i;
return r;
}
ii front(){ return T[1]; }
ii back(){ return T[i_back()]; }
void pop_front(){ pop(1); }
void pop_back(){ pop(i_back()); }
void show(){
int i;
for (i=1; i<=n; i++){
for (int j=1<<5-level(i); j>=3; j--) printf(" ");
if (i&i+1) printf(" %d", T[i]);
else printf(" %d\n", T[i]);
}
}
};
min_max_heap tr;
main(){
int ch, p, q;
while (scanf("%d", &ch) > 0){
if (ch==0) tr.show();
if (ch==1) {
scanf("%d%d", &p, &q);
tr.push(ii(q, p));
}
if (ch==2) {
if (tr.n==0) printf("0\n");
else {
printf("%d\n", tr.back().second);
tr.pop_back();
}
}
if (ch==3) {
if (tr.n==0) printf("0\n");
else {
printf("%d\n", tr.front().second);
tr.pop_front();
}
}
}
}
Nhận xét
Code này đã được dùng để nộp cho một bài trên SPOJ.