posts - 1,  comments - 0,  trackbacks - 0
  2008年9月2日
JAVA实现的Heap
@SuppressWarnings("unused")
public class MyHeap{
    
    private static final int MAX_SIZE = 1001;

    private int CUR_SIZE;      
   
    private Comparable[] DATA;
    
    public MyHeap() {
        CUR_SIZE = 0;
        DATA = new Comparable[ MAX_SIZE + 1 ];
    }
    
    public MyHeap( Comparable [] items ) {
        CUR_SIZE = items.length;
        DATA = new Comparable[ items.length + 1 ];
        
        for( int i = 0; i < items.length; i++ )
            DATA[ i + 1 ] = items[ i ];
        buildHeap();
    }
    
    public void insert( Comparable x ) {
        if( CUR_SIZE + 1 == DATA.length )
            doubleArray( );
        
        // Percolate up
        int hole = ++CUR_SIZE;
        DATA[ 0 ] = x;
        
        for( ; x.compareTo( DATA[ hole / 2 ] ) < 0; hole /= 2 ) {
            DATA[ hole ] = DATA[ hole / 2 ];
        }
        DATA[ hole ] = x;
    }
    
    public Comparable findMin( ) {
        return DATA[ 1 ];
    }
    
    public Comparable deleteMin( ) {
        Comparable minItem = findMin( );
        DATA[ 1 ] = DATA[ CUR_SIZE-- ];
        percolateDown( 1 );
        
        return minItem;
    }
    
    private void buildHeap( ) {
        for( int i = CUR_SIZE / 2; i > 0; i-- )
            percolateDown( i );
    }
    
    public boolean isEmpty( ) {
        return CUR_SIZE == 0;
    }
    
    public int size( ) {
        return CUR_SIZE;
    }
    
    public void makeEmpty( ) {
        CUR_SIZE = 0;
    }
    
    private void percolateDown( int hole ) {
        int child;
        Comparable tmp = DATA[ hole ];
        
        for( ; hole * 2 <= CUR_SIZE; hole = child ) {
            child = hole * 2;
            if( child != CUR_SIZE &&
                    DATA[ child + 1 ].compareTo( DATA[ child ] ) < 0 )
                child++;
            if( DATA[ child ].compareTo( tmp ) < 0 )
                DATA[ hole ] = DATA[ child ];
            else
                break;
        }
        DATA[ hole ] = tmp;
    }    
    
    private void doubleArray( ) {
        Comparable [] newArray;
        
        newArray = new Comparable[ DATA.length * 2 ];
        for( int i = 0; i < DATA.length; i++ )
            newArray[ i ] = DATA[ i ];
        DATA = newArray;
    }
}
posted @ 2008-09-02 15:51 水牛♂Toto 阅读(209) | 评论 (0) | 编辑 收藏
Powered by:
BlogJava
Copyright ©2024 水牛♂Toto