RS_FHeap.h
Fibonacci Heap の実装
RS_FHeap.h
—
C header,
17 kB (17544 bytes)
ファイルコンテンツ
// This may look like C code, but it is really -*- C++ -*- // RTSS --- Railway Total System Simulator // (c) TAKAGI Ryo (at Kogakuin University) // RS_FHeap.h --- class RS_FHeap, Fibonacci Heap // ----- // ChangeLog: // 2009. 7. 15 // File complete. // ----- // ---- // Heap // ヒープ // ---- #ifndef RS_FHEAP_H #define RS_FHEAP_H #include <iostream> #include <cstdlib> #include <cmath> #include <vector> #include <string> using std :: cerr ; using std :: endl ; using std :: vector ; using std :: string ; //#define DEBUG_FHEAP template < class KC , class ENT > class RS_FHeap { public : typedef unsigned int size_type ; class Entry { friend class RS_FHeap ; private : KC _key ; ENT * _ent ; typename RS_FHeap :: size_type _deg ; bool _marked ; typename RS_FHeap :: Entry * _right ; typename RS_FHeap :: Entry * _left ; typename RS_FHeap :: Entry * _parent ; typename RS_FHeap :: Entry * _child ; RS_FHeap * _myheap ; void cutFromChildList () ; void execCascadingCut () ; void addToChildList ( Entry * ) ; explicit Entry () ; explicit Entry ( const Entry & ) ; public : Entry ( const KC & x , ENT * _e , RS_FHeap * hp ) : _key ( x ) , _ent ( _e ) , _deg ( 0 ) , _marked ( false ) , _right ( this ) , _left ( this ) , _parent ( 0 ) , _child ( 0 ) , _myheap ( hp ) {} void decreaseKey ( const KC & ) ; const KC & getKey () const { return _key ; } Entry * getRight () { return _right ; } Entry * getLeft () { return _left ; } Entry * getParent () { return _parent ; } Entry * getChild () { return _child ; } typename RS_FHeap :: size_type getDegree () const { return _deg ; } typename RS_FHeap :: size_type countEntriesInMe () const ; #ifdef DEBUG_FHEAP void printChildren ( unsigned int = 0 ) const ; #endif ENT * getEntryData () { return _ent ; } const ENT * getEntryData () const { return _ent ; } } ; friend class Entry ; private : typename RS_FHeap :: Entry * _min ; size_type _num ; mutable size_type _d_cal ; mutable size_type _num_d_cal ; vector < typename RS_FHeap :: Entry * > cvec ; size_type getD () const ; void putIntoRoot ( RS_FHeap :: Entry * ) ; void execConsolidate () ; public : explicit RS_FHeap () : _min ( 0 ) , _num ( 0 ) , _d_cal ( 0 ) , _num_d_cal ( 0 ) , cvec () {} Entry * getMinimum () const { return _min ; } void insert ( RS_FHeap :: Entry * ) ; Entry * deleteMinimum () ; size_type size () const { return _num ; } } ; // ---- // Some implementation of class Heap // ヒープクラスの実装の一部 // ---- template < class KC , class ENT > void RS_FHeap < KC , ENT > :: putIntoRoot ( typename RS_FHeap < KC , ENT > :: Entry * _new ) { #ifdef DEBUG_FHEAP cerr << "putIntoRoot: start, entry = " << * ( _new -> getEntryData () ) << "(" << * ( _new -> getLeft () -> getEntryData () ) << " - " << * ( _new -> getEntryData () ) << " - " << * ( _new -> getRight () -> getEntryData () ) << ")"<< endl ; #endif if ( _min ) { #ifdef DEBUG_FHEAP cerr << "putIntoRoot: _min = " << * ( _min -> getEntryData () ) << "(" << * ( _min -> getLeft () -> getEntryData () ) << " - " << * ( _min -> getEntryData () ) << " - " << * ( _min -> getRight () -> getEntryData () ) << ")"<< endl ; #endif _min -> _left -> _right = _new ; _new -> _left = _min -> _left ; _new -> _right = _min ; _min -> _left = _new ; if ( _new -> _key < _min -> _key ) { _min = _new ; } } else { #ifdef DEBUG_FHEAP cerr << "putIntoRoot: _min not found, heap size = " << _num << endl ; #endif _min = _new ; } #ifdef DEBUG_FHEAP cerr << "putIntoRoot: finished, entry = " << * ( _new -> getEntryData () ) << "(" << * ( _new -> getLeft () -> getEntryData () ) << " - " << * ( _new -> getEntryData () ) << " - " << * ( _new -> getRight () -> getEntryData () ) << ")"<< endl ; #endif } template < class KC , class ENT > typename RS_FHeap < KC , ENT > :: size_type RS_FHeap < KC , ENT > :: Entry :: countEntriesInMe () const { typename RS_FHeap :: size_type _retv = 1 ; if ( _child ) { Entry * _csc = _child ; do { _retv += _csc -> countEntriesInMe () ; _csc = _csc -> _right ; } while ( _csc != _child ) ; } return _retv ; } template < class KC , class ENT > void RS_FHeap < KC , ENT > :: Entry :: cutFromChildList () { #ifdef DEBUG_FHEAP cerr << "cut: object = " << * ( getEntryData () ) << "<" << getDegree () << ">, parent = " << * ( _parent -> getEntryData () ) << "<" << _parent -> getDegree () << ">" << endl ; #endif -- ( _parent -> _deg ) ; _right -> _left = _left ; _left -> _right = _right ; if ( _parent -> _child == this ) { #ifdef DEBUG_FHEAP cerr << "cut: parent's child pointer points to this" << endl ; #endif if ( this -> _right == this ) { #ifdef DEBUG_FHEAP cerr << "cut: no child must be present, degree actually = " << _parent -> getDegree () << endl ; #endif _parent -> _child = 0 ; } else { _parent -> _child = _left ; } } _left = _right = this ; _parent = 0 ; _marked = false ; _myheap -> putIntoRoot ( this ) ; } #ifdef DEBUG_FHEAP template < class KC , class ENT > void RS_FHeap < KC , ENT > :: Entry :: printChildren ( unsigned int _indent /* = 0 */ ) const { if ( _child ) { Entry * _csc = _child ; do { for ( unsigned int i = 0 ; i < _indent ; ++ i ) { cerr << " " ; } cerr << "+--" << * ( _csc -> getEntryData () ) << "<" << _csc -> getDegree () << ">[" << _csc -> getKey () << "](" << _csc -> countEntriesInMe () << ")" << endl ; _csc -> printChildren ( _indent + 1 ) ; _csc = _csc -> _right ; } while ( _csc != _child ) ; } } #endif template < class KC , class ENT > void RS_FHeap < KC , ENT > :: Entry :: execCascadingCut () { if ( _parent ) { #ifdef DEBUG_FHEAP cerr << "cascading cut: parent: " << * ( _parent -> getEntryData () ) << "[" << _parent -> getKey () << "]" ; if ( _parent -> _marked ) cerr << "[M]" ; cerr << endl ; #endif if ( _parent -> _marked ) { #ifdef DEBUG_FHEAP cerr << "parent has been marked, cut from child list" << endl ; #endif typename RS_FHeap < KC , ENT > :: Entry * px = _parent ; cutFromChildList () ; px -> execCascadingCut () ; } else { #ifdef DEBUG_FHEAP cerr << "mark parent: " << * ( _parent -> getEntryData () ) << "[" << _parent -> getKey () << "]" ; if ( _parent -> _marked ) cerr << "[M]" ; #endif _parent -> _marked = true ; #ifdef DEBUG_FHEAP cerr << " -> " << * ( _parent -> getEntryData () ) << "[" << _parent -> getKey () << "]" ; if ( _parent -> _marked ) cerr << "[M]" ; cerr << endl ; #endif } } else { #ifdef DEBUG_FHEAP cerr << "cascading cut: no parent. done." << endl ; #endif } } template < class KC , class ENT > void RS_FHeap < KC , ENT > :: Entry :: decreaseKey ( const KC & x ) { if ( _key < x ) { cerr << "Error: Heap::Entry::decreaseKey(...): new key must be smaller " << "than the original key" << endl ; exit ( 1 ) ; } _key = x ; #ifdef DEBUG_FHEAP cerr << "decreaseKey: key set" << endl ; #endif if ( _parent ) { #ifdef DEBUG_FHEAP cerr << "parent exists" << endl ; #endif if ( _key < _parent -> getKey () ) { #ifdef DEBUG_FHEAP cerr << "parent has larger key" << endl ; #endif typename RS_FHeap < KC , ENT > :: Entry * px = _parent ; #ifdef DEBUG_FHEAP cerr << "before cut" << endl ; #endif cutFromChildList () ; #ifdef DEBUG_FHEAP cerr << "before cascading cut" << endl ; #endif px -> execCascadingCut () ; #ifdef DEBUG_FHEAP cerr << "cut complete" << endl ; #endif } } else { #ifdef DEBUG_FHEAP cerr << "parent does not exist" << endl ; #endif } if ( _myheap -> _min -> _key > x ) { #ifdef DEBUG_FHEAP cerr << "this is the minimum entry" << endl ; #endif _myheap -> _min = this ; } } template < class KC , class ENT > typename RS_FHeap < KC , ENT > :: Entry * RS_FHeap < KC , ENT > :: deleteMinimum () { typename RS_FHeap < KC , ENT > :: Entry * ret_val = _min ; #ifdef DEBUG_FHEAP cerr << "deleteMin starts, current heap size: " << _num << " elements" << endl ; #endif while ( _min -> _child ) { #ifdef DEBUG_FHEAP cerr << "deleteMin: child found, _min = " << * ( _min -> getEntryData () ) << endl ; typename RS_FHeap < KC , ENT > :: Entry * _mc = _min -> _child ; typename RS_FHeap < KC , ENT > :: Entry * _mp = _mc -> _parent ; cerr << "child: " << _mc -> getKey () << " [" << _mc -> getDegree () << "]: " << * ( _mc -> getEntryData () ) << " (" << * ( _mc -> getLeft () -> getEntryData () ) << " - " << * ( _mc -> getEntryData () ) << " - " << * ( _mc -> getRight () -> getEntryData () ) << ")" << endl ; cerr << "child's parent: " << _mp -> getKey () << " [" << _mp -> getDegree () << "]: " << * ( _mp -> getEntryData () ) << " (" << * ( _mp -> getLeft () -> getEntryData () ) << " - " << * ( _mp -> getEntryData () ) << " - " << * ( _mp -> getRight () -> getEntryData () ) << ")" << endl ; #endif _min -> _child -> cutFromChildList () ; } #ifdef DEBUG_FHEAP cerr << "deleteMin: no child list, _min = " << * ( _min -> getEntryData () ) << endl ; #endif if ( ret_val -> _right == ret_val ) { #ifdef DEBUG_FHEAP cerr << "deleteMin: right of ret_val is ret_val: _num should be 1, " << "actually: " << _num << endl ; #endif _min = 0 ; } else { #ifdef DEBUG_FHEAP cerr << "deleteMin: set _min to _right of ret_val, " << * ( ret_val -> _right -> getEntryData () ) << endl ; #endif _min = ret_val -> _right ; ret_val -> _right -> _left = ret_val -> _left ; ret_val -> _left -> _right = ret_val -> _right ; execConsolidate () ; } -- _num ; #ifdef DEBUG_FHEAP if ( _min ) { cerr << "deleteMin: root list" << endl ; typename RS_FHeap < KC , ENT > :: Entry * _nc = _min ; typename RS_FHeap < KC , ENT > :: size_type _cx = 0 ; do { cerr << * ( _nc -> getEntryData () ) << "<" << _nc -> getDegree () << ">[" << _nc -> getKey () << "](" << _nc -> countEntriesInMe () << ")" << endl ; _nc -> printChildren () ; _nc = _nc -> _right ; _cx += _nc -> countEntriesInMe () ; } while ( _nc != _min ) ; cerr << "_num, _num actually: " << _num << ", " << _cx << endl ; } else { cerr << "deleteMin: root list empty" << endl << "_num, _num actually: " << _num << ", 0" << endl ; } #endif return ret_val ; } template < class KC , class ENT > typename RS_FHeap < KC , ENT > :: size_type RS_FHeap < KC , ENT > :: getD () const { if ( _num_d_cal == _num ) { return _d_cal ; } _num_d_cal = _num ; double _dn = log ( _num ) / log ( ( 1 + sqrt ( 5 ) ) / 2 ) ; if ( _dn < 0 ) _dn = 0 ; return ( _d_cal = static_cast < size_type > ( ceil ( _dn ) ) ) ; } template < class KC , class ENT > void RS_FHeap < KC , ENT > :: execConsolidate () { #ifdef DEBUG_FHEAP cerr << "consolidation starts, getD: " << getD () << endl ; #endif cvec . assign ( getD () , 0 ) ; typename RS_FHeap < KC , ENT > :: Entry * _nw = _min ; typename RS_FHeap < KC , ENT > :: Entry * _minx = _min ; do { _min = _minx ; #ifdef DEBUG_FHEAP cerr << "check: " << _nw -> getKey () << " [" << _nw -> getDegree () << "]: " << * ( _nw -> getEntryData () ) << " (" << * ( _nw -> getLeft () -> getEntryData () ) << " - " << * ( _nw -> getEntryData () ) << " - " << * ( _nw -> getRight () -> getEntryData () ) << ")" << endl ; #endif typename RS_FHeap < KC , ENT > :: Entry * _nx = _nw ; _nw = _nw -> _right ; while ( _nx -> _deg >= cvec . size () ) { cerr << "Warning: degree vector not sufficient, deg, size =" << _nx -> _deg << ", " << cvec . size () << endl ; cvec . push_back ( 0 ) ; } size_type _d = _nx -> _deg ; #ifdef DEBUG_FHEAP cerr << "_min degree: " << _d << endl ; #endif if ( cvec [ _d ] == _nx ) { cerr << "Warning: this degree checked, continue" << endl ; continue ; } while ( cvec [ _d ] ) { typename RS_FHeap < KC , ENT > :: Entry * _ny = cvec [ _d ] ; #ifdef DEBUG_FHEAP cerr << "degree " << _d << " already there, " ; cerr << _ny -> getKey () << " [" << _ny -> getDegree () << "]: " << * ( _ny -> getEntryData () ) << " (" << * ( _ny -> getLeft () -> getEntryData () ) << " - " << * ( _ny -> getEntryData () ) << " - " << * ( _ny -> getRight () -> getEntryData () ) << ")" << endl ; #endif if ( _ny -> _key < _nx -> _key ) { typename RS_FHeap < KC , ENT > :: Entry * _nz = _nx ; _nx = _ny ; _ny = _nz ; #ifdef DEBUG_FHEAP cerr << "exchanged nx and ny, ny = " ; cerr << _ny -> getKey () << " [" << _ny -> getDegree () << "]: " << * ( _ny -> getEntryData () ) << " (" << * ( _ny -> getLeft () -> getEntryData () ) << " - " << * ( _ny -> getEntryData () ) << " - " << * ( _ny -> getRight () -> getEntryData () ) << ")" << endl ; #endif } if ( _ny == _minx ) { _minx = _minx -> _right ; } #ifdef DEBUG_FHEAP cerr << "before addtochildlist, _nx: " << _nx -> getKey () << " [" << _nx -> getDegree () << "]: " << * ( _nx -> getEntryData () ) << " (" << * ( _nx -> getLeft () -> getEntryData () ) << "<" << _nx -> getLeft () -> getDegree () << ">" << " - " << * ( _nx -> getEntryData () ) << " - " << * ( _nx -> getRight () -> getEntryData () ) << "<" << _nx -> getRight () -> getDegree () << ">" << ")" ; if ( _nx -> _child ) { cerr << " (child: " ; string x_str = "" ; typename RS_FHeap < KC , ENT > :: Entry * _nc = _nx -> _child ; do { cerr << x_str << * ( _nc -> getEntryData () ) << "<" << _nc -> getDegree () << ">" ; x_str = " - " ; _nc = _nc -> _right ; } while ( _nc != _nx -> _child ) ; cerr << ")" ; } cerr << endl ; #endif _ny -> _right -> _left = _ny -> _left ; _ny -> _left -> _right = _ny -> _right ; _ny -> _right = _ny -> _left = _ny ; _nx -> addToChildList ( _ny ) ; #ifdef DEBUG_FHEAP cerr << "after addtochildlist, _nx: " << _nx -> getKey () << " [" << _nx -> getDegree () << "]: " << * ( _nx -> getEntryData () ) << " (" << * ( _nx -> getLeft () -> getEntryData () ) << "<" << _nx -> getLeft () -> getDegree () << ">" << " - " << * ( _nx -> getEntryData () ) << " - " << * ( _nx -> getRight () -> getEntryData () ) << "<" << _nx -> getRight () -> getDegree () << ">" << ")" ; if ( _nx -> _child ) { cerr << " (child: " ; string x_str = "" ; typename RS_FHeap < KC , ENT > :: Entry * _nc = _nx -> _child ; do { cerr << x_str << * ( _nc -> getEntryData () ) << "<" << _nc -> getDegree () << ">" ; x_str = " - " ; _nc = _nc -> _right ; } while ( _nc != _nx -> _child ) ; cerr << ")" ; } cerr << endl ; #endif cvec [ _d ] = 0 ; ++ _d ; } #ifdef DEBUG_FHEAP cerr << "degree " << _d << ": this one" << endl ; #endif cvec [ _d ] = _nx ; } while ( _nw != _min ) ; _min = 0 ; #ifdef DEBUG_FHEAP cerr << "before search, _min set to Null" << endl ; #endif for ( vector < size_type > :: size_type i = 0 ; i < cvec . size () ; ++ i ) { #ifdef DEBUG_FHEAP cerr << "degree " << i << " scanning" << endl ; #endif if ( cvec [ i ] ) { #ifdef DEBUG_FHEAP cerr << "degree " << i << " found: " << * ( cvec [ i ] -> getEntryData () ) << "[" << cvec [ i ] -> getKey () << "]" << endl ; #endif if ( ! _min || cvec [ i ] -> _key < _min -> _key ) { #ifdef DEBUG_FHEAP cerr << " ... this is the new minimum" << endl ; #endif _min = cvec [ i ] ; } } } #ifdef DEBUG_FHEAP cerr << "end: " << _min -> getKey () << " [" << _min -> getDegree () << "]: " << * ( _min -> getEntryData () ) << " (" << * ( _min -> getLeft () -> getEntryData () ) << " - " << * ( _min -> getEntryData () ) << " - " << * ( _min -> getRight () -> getEntryData () ) << ")" << endl ; cerr << "consolidation ended" << endl ; #endif } template < class KC , class ENT > void RS_FHeap < KC , ENT > :: insert ( RS_FHeap < KC , ENT > :: Entry * _in ) { putIntoRoot ( _in ) ; ++ _num ; } template < class KC , class ENT > void RS_FHeap < KC , ENT > :: Entry :: addToChildList ( typename RS_FHeap < KC , ENT > :: Entry * _in ) { if ( _child ) { _child -> _left -> _right = _in ; _in -> _left = _child -> _left ; _child -> _left = _in ; _in -> _right = _child ; } else { _child = _in ; } _in -> _parent = this ; ++ _deg ; } #endif // RS_FHEAP_H