최대히프를 구현해 보았다.
트리의 배열 표현에 대한 선행 지식이 있어야한다.
//################################################################### //
//------------------------< 베열을 이용한 히프 구현 >---------------------------- //
//구성 : 최초 배열 사이즈는 1이다. 인덱스 0에는 헤더값이 저장된다. ###############//
//단점 : 배열의 요소가 하나 추가될 때 마다 배열 크기를 늘리기위한 연산이 수행된다## //
// add()함수를 1만번 호출해 본 결과 평균 380m/s가 소요되었다.#############//
// deleteMax()함 함수의 호출 결과과 역시 비슷한 시간이 소요되었다.##########//
//################################################################## //
public class HeapArray{
public HeapArray(){
Heap heap= new Heap();
heap.add(10);
heap.add(20);
heap.add(30);
heap.add(40);
heap.add(50);
heap.add(60);
heap.add(70);
heap.add(80);
heap.numberorder();
System.out.println("--Delete Max--");
heap.deleteMax();
heap.numberorder();
}
public static void main(String args[]){
HeapArray ha= new HeapArray();
}
};
//###################################################################//
//--------------------------< 히프를 구현한 클래스 >-----------------------------//
//히프의 추가, 삭제, 복사, 출력등 히프에 관한 전반적인 연산이 구현되어있다.########//
//##################################################################//
class Heap{
private int heapTree[]= new int[1];
//###################################################################//
//--------------------------------< 생성자 >------------------------------------//
//##################################################################//
public Heap(){
heapTree[0]=0;
}
//####################################################################//
//----------------------------< 엘리먼트 추가 >----------------------------------//
//###################################################################//
public void add(int data){
//엘리먼트를 추가 : 추가시 배열의 크기가 증가하므로, 크기가 1 증가한 새로운 배열 생성.
int newTree[]= new int[heapTree.length+1];
//엘리먼트 복사 : 크기가 1 증가한 새로운 트리에 기존의 내용을 모두 복사한다.
for(int i=1;i<heapTree.length;i++){
newTree[i]= heapTree[i];
}
//추가한 값 저장. 새로 생성한 배열의 마지막에 엘리먼트를 하나 추가
newTree[heapTree.length]=data;
//기존 배열을 새로 생성한 배열로 바꾼다.
heapTree= newTree;
//최대 히프 작업을 한다.
int pos=heapTree.length-1;
while(pos!=1){
//부모노드 보다 자식노드의 값이 크면 두 노드값을 교체한다.
if(heapTree[pos]>heapTree[pos/2]){
int buf= heapTree[pos];
heapTree[pos]=heapTree[pos/2];
heapTree[pos/2]=buf;
}else{
break;
}
pos=pos/2; //부모노드로 이동.
}
}
//####################################################################//
//-----------------------------< 최대값 삭제 >-----------------------------------//
//###################################################################//
public void deleteMax(){
heapTree[1]=heapTree[heapTree.length-1];
int pos=1;
while((pos*2+1)<heapTree.length-1){
//부모노드가 자식노드 보다 작은 경우
if(heapTree[pos*2]>heapTree[pos] || heapTree[pos*2+1]>heapTree[pos]){
//부모노드를 기준으로 좌 우 노드중 좌 노드가 우 노드 보다 큰 경우
if(heapTree[pos*2]>heapTree[pos*2+1]){
int buf= heapTree[pos];
heapTree[pos]=heapTree[pos*2];
heapTree[pos*2]=buf;
pos=pos*2;
}else{ //부모노드를 기준으로 좌 우 노드중 우 노드가 좌 노드 보다 큰 경우
int buf= heapTree[pos];
heapTree[pos]=heapTree[pos*2+1];
heapTree[pos*2+1]=buf;
pos=pos*2+1;
}
}else{
break;
}
}
//노드가 하나 삭제 되면, 배열의 크기가 줄어들게 된다.
//따라서 삭제전 배열 보다 크기가 1 작은 새로운 노드를 생성하여야 한다.
int newTree[]= new int[heapTree.length-1];
for(int i=1;i<newTree.length;i++){
newTree[i]= heapTree[i];
}
heapTree=newTree;
}
//엘리먼트를 배열에 저장된 순서대로 출력한다.
public void numberorder(){
for(int i=1;i<heapTree.length;i++){
System.out.println(heapTree[i]);
}
}
};
'Computer > Java' 카테고리의 다른 글
Static on Java- Speed Test (0) | 2006.10.09 |
---|---|
[Data Structure2] Binary Tree (Linked List) (0) | 2006.10.09 |
[tip] 화면 크기 구하기. (0) | 2006.08.04 |
Omok Server For Flash Client Ver1.0 (0) | 2006.07.23 |
Cyworld Today Counter Hack ver2.0(GUI Version) by DogBull (0) | 2006.07.23 |