05-7 힙의 구현

Main

public class Main {

       public static void main(String[] args) {

              int n, item;

              MaxHeap h = new MaxHeap();

              h.insertHeap(13);

              h.insertHeap(8);

              h.insertHeap(10);

              h.insertHeap(15);

              h.insertHeap(20);

              h.insertHeap(19);

              h.insertHeap(30);

              h.printHeap();

              n=h.getHeapSize();

              for(int i=1; i<=n ; i++){

                     item = h.deleteHeap();

                     System.out.println("\n delete Item : [" + item + "]" );

              }

       }

}

MaxHeap

public class MaxHeap {

       private int[] heap;

       private int heapSize;

       public MaxHeap() {

              // TODO Auto-generated constructor stub

              heap = new int[50];

              heapSize =0;

       }

       public void insertHeap(int x){

              int idx = ++heapSize;

              int temp;

              heap[idx] = x;

              while(idx != 1 && heap[idx] > heap[idx/2]){

                     temp = heap[idx/2];

                     heap[idx/2] = heap[idx];

                     heap[idx] = temp;

                     idx = idx/2;

              }

       }

       public void printHeap(){

              for(int i = 1; i<=heapSize ; i++){

                     System.out.print("["+heap[i]+"]");

              }

       }

       public int deleteHeap(){

              if(isEmpty()){

                     return 0;

              }

              int rootValue = heap[1];

              heap[1] = heap[heapSize];

              heapSize --;

              int idx =1;

              int temp;

              while(idx*2 <=heapSize || idx*2+1 <= heapSize){

                     if(heap[idx*2] > heap[idx*2+1]){

                           temp = heap[idx*2];

                           heap[idx*2] = heap[idx];

                           heap[idx]= temp;

                           idx = idx*2;

                     }else if(heap[idx*2] < heap[idx*2+1]){

                           temp = heap[idx*2+1];

                           heap[idx*2+1] = heap[idx];

                           heap[idx]= temp;

                           idx = idx*2+1;

                     }

              }

              return rootValue;

       }

       public boolean isEmpty(){

              return heapSize==0;

       }

       public int getHeapSize(){

              return heapSize;

       }

}