Skew Heap
コードについての説明(個人的メモ)
併合操作を効率的行うことのできるヒープ. とても簡単な実装でならし $\O (\log n)$ を達成することができる.
大きい方が top にくる実装にしているが, meld の中の不等号を変えることで小さいほうが top に変更可能.
(関数)
empty(): ヒープが空かどうか
size(): ヒープ内の要素数を返す
push$(val)$: 要素 $val$ を追加する
top(): ヒープ内の最大値を返す
pop(): ヒープ内の最大値を削除する
meld$(a, b)$: ヒープ $a$, ヒープ $b$ を併合して, 新しく出来たヒープのポインタを返す
時間計算量: empty(), size(), top(): $\O (1)$, push(), pop(), meld(): ならし $\O (\log n)$
コード
template<typename T> class node {
public:
node<T>* l; node<T>* r; T val;
node(T t) : l(nullptr), r(nullptr), val(t){}
friend node* meld(node* a, node* b){
if(!a) return b;
if(!b) return a;
if(a->val < b->val) swap(a, b);
a->l = meld(a->l,b);
swap(a->l, a->r);
return a;
}
};
template<typename T> class Heap {
public:
node<T>* root;
int sz;
Heap() : root(nullptr), sz(0){}
bool empty(){
return !root;
}
int size(){
return sz;
}
void push(T val){
sz++;
node<T>* p = new node<T>(val);
root = meld(root, p);
}
T top(){
return root->val;
}
void pop(){
sz--;
node<T>* p = root;
root = meld(root->r, root->l);
delete p;
}
friend Heap<T>* meld(Heap<T>* hp1, Heap<T>* hp2){
Heap<T>* res = new Heap<T>();
res->sz = hp1->sz + hp2->sz;
res->root = meld(hp1->root, hp2->root);
return res;
}
};
verify 用の問題
AOJ : Minimum Spanning Tree 提出コード