4
방금 짝을 이루는 힙 데이터 구조를 구현했습니다. Pairing heap은 O (logN) 상각 시간에서 O (1) amortized time 및 delete, delete-min에 insert, find-min, merge를 지원합니다. 그러나 가장 현저한 연산은 복잡성 O (로그 logN)를 갖는 감소 키입니다. 페어링 힙에 대한 자세한 내용은 http://en.wikipedia.org/wiki/Pairing_heap에서 확인할 수 있습니다.페어링 힙 - 감소 키 구현
삽입, 병합 및 삭제 작업을 구현했지만 위키피디아 문서에서는 주어진 노드의 키를 줄이는 방법을 언급하지 않았으므로이를 구현할 수 없었습니다. 누군가 실제로 어떻게 작동하는지 말할 수 있습니까? 다음과 같이 the original paper on pairing heaps, page 114에 따르면
template< class key_t, class compare_t=std::less<key_t> >
struct pairing_heap {
private:
struct node {
key_t key; std::vector< node* > c;
node(key_t k=key_t()) : key(k), c(std::vector< node* >()) {}
};
node *root;
compare_t cmp;
unsigned sz;
public:
typedef key_t value_type;
typedef compare_t compare_type;
typedef pairing_heap< key_t, compare_t > self_type;
pairing_heap() : root(0) {}
node* merge(node *x, node *y) {
if(!x) return y;
else if(!y) return x;
else {
if(cmp(x->key, y->key)) {
x->c.push_back(y);
return x;
} else {
y->c.push_back(x);
return y;
}
}
}
node* merge_pairs(std::vector< node* > &c, unsigned i) {
if(c.size()==0 || i>=c.size()) return 0;
else if(i==c.size()-1) return c[ i ];
else {
return merge(merge(c[ i ], c[ i+1 ]), merge_pairs(c, i+2));
}
}
void insert(key_t x) {
root = merge(root, new node(x));
sz++;
}
key_t delmin() {
if(!root) throw std::runtime_error("std::runtime_error");
key_t ret=root->key;
root = merge_pairs(root->c, 0);
sz--;
return ret;
}
bool empty() const { return root==0; }
unsigned size() const { return sz; }
};