I just implemented the pairing heap data structure. Pairing heap supports insert, find-min, merge in O(1) amortized time and delete, delete-min in O(logN) amortized time. But the most remarkable operation is the decrease-key, which has complexity O(log logN). More about pairing heaps can be found at http://en.wikipedia.org/wiki/Pairing_heap.
I have implemented the insert, merge, and delete-min operations, but the wikipedia article didn't say how to decrease a key of a given node, so I couldn't implement it. Could someone tell me how it actually works?
Here is my code:
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; }
};
In this tutorial, we'll present a third operation called decrease-key, which allows us to decrease the value of a certain key inside the data structure. Mainly, the decrease-key operation is used in Dijkstra's algorithm when we discover a new path to a certain node at a lower cost.
How is a pairing heap represented? Explanation: A pairing heap is represented as a heap-ordered tree and the analysis of pairing heap is open.
According to the original paper on pairing heaps, page 114, the decrease-key operation is implemented as follows. First, change the priority of the node whose key is to be decreased to have the new priority. If its priority is still greater than its parent (or if it's the root of the tree), you are done. Otherwise, cut the link from that node to its parent, then use the merge operation to combine the original heap with the subtree that was just cut from that tree.
Hope this helps!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With