[Data Structure2] Max Heap (for int array)

최대히프를 구현해 보았다.
트리의 배열 표현에 대한 선행 지식이 있어야한다.

//################################################################### //
//------------------------< 베열을 이용한 히프 구현 >---------------------------- //
//구성 : 최초 배열 사이즈는 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]);
       }
  }
};