我刚刚实现了配对堆数据结构。 配对堆支持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; }
};