4
我剛剛實現了配對堆數據結構。配對堆支持插入，find-min，O（1）分攤時間合併和刪除，O（logN）分攤時間中的刪除分鐘。但最顯着的操作是複雜度爲O（log logN）的遞減密鑰。有關配對堆的更多信息，請參閱http://en.wikipedia.org/wiki/Pairing_heap。配對堆 - 執行減少鍵
我已經實現了插入，合併，並刪除最小操作，但維基百科的文章並沒有說如何減少給定節點的關鍵，所以我無法實現它。有人能告訴我它是如何工作的嗎？
這裏是我的代碼：
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; }
};