JAVA实现的Heap

水牛♂Toto — Tue, 02 Sep 2008 07:51:00 GMT

@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;
    }
}

水牛♂Toto 2008-09-02 15:51 发表评论

语源科技BlogJava-Algorithm in Java.

JAVA实现的Heap