posts - 1, 
comments - 0, 
trackbacks - 0


          
	

          


          
	
					


          
	
	
          @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 on 2008-09-02 15:51 水牛♂Toto 閱讀(215) 評論(0)  編輯  收藏  
          

          







          
	    
    




          





          


          

	
          
		
          
				
		
	
		
          
		
		
          只有注冊用戶登錄后才能發表評論。
          
		
          
			
		
          
			
		
          
		
		
          
		


          

		          		
		
          
		
          			
		
		
		
		
          
		
          
		
		
          
		
          
			網站導航:
		
		
          
		
          
			
		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				

          





    







          
        
	




主站蜘蛛池模板：
神木县|
高邮市|
县级市|
会昌县|
兰考县|
大同市|
郧西县|
临城县|
吉安县|
重庆市|
余姚市|
晋宁县|
华池县|
桃园市|
永登县|
开鲁县|
江阴市|
大同市|
通道|
尼勒克县|
连城县|
滦南县|
敦煌市|
彭州市|
鸡东县|
彭水|
衡南县|
额济纳旗|
满洲里市|
津南区|
洪江市|
若羌县|
岳普湖县|
广汉市|
邢台县|
白山市|
确山县|
育儿|
铁岭县|
平和县|
安陆市|