Algorithm in Java.

BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

posts - 1, comments - 0, trackbacks - 0

<

2025年6月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

常用鏈接

留言簿(1)

隨筆檔案

2008年9月 (1)

搜索

最新評論

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 閱讀(215) | 評論 (0) | 編輯收藏

僅列出標題