Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Pairing heap - implementation of decrease key

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; }
};
like image 264
Rontogiannis Aristofanis Avatar asked Dec 18 '12 19:12

Rontogiannis Aristofanis


People also ask

What is decrease-key operation in heap?

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?

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.


1 Answers

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!

like image 142
templatetypedef Avatar answered Sep 18 '22 00:09

templatetypedef