[백준] 11279 최대 힙

문제보기

자료구조 내용은 추후 따로 정리하겠지만, 어쨋든 처음 구현해본 힙!

import java.util.*;
import java.io.*;

public class Main{

  // 힙 - 삽입하기
  public static void insertHeap(int[] heap, int size, int item){
    int i = ++size;

    while(true){
      if( i == 1 ){ // 크기가 비어있다면 바로 넣어주면 됨 
        break;
      }
      if( item < heap[i/2]){ // 만일 부모보다 작다면 바로 넣어주면 됨 
        break;
      }
      // 여기까지 왔다면 얜 부모보다 큰애다
      heap[i] = heap[i/2];  // 부모 자리로 올라가야 하지만, 일단 부모부터 아래로 끌어내리자..
      i = i/2; // 자, 이제 위치는 부모 자리로 재 설정 되었다
    }
    // 그 자리에 넣을 숫자를 넣는다
    heap[i] = item;
  }

  // 힙 - 삭제 연산
  public static int deleteHeap(int[] heap, int size){
		
    // 삭제 할 원소가 없다면 0을 반환하는게 문제 조건이다
    if( size == 0 ){
      return 0;
    }
    // 일단 루트값을 최후에 반환해야 하므로 미리 빼준다 
    int item = heap[1];
    // 루트자리에 최 말단 원소를 넣는다
    heap[1] = heap[size];
    // 힙 사이즈는 하나 줄여주고, 마지막 원소 자리는 0으로 비운다
    heap[size--] = 0;
		
    // 자 이제 대망의!! 재정렬하기!! 이거때문에 몇시간을 허비했는지 모르겠다 ^^
    // 흑흑... 자 일단 기본적인 재정렬의 원리는 이렇다.
    // 위의 식을 통해 우리는 마지막 원소를 루트 자리로 보냈다.
    // 이 아이를 적절한 위치로 보내주는 과정을 통해 재정렬이 된다.
    // 우선 이 아이의 초기 위치는 루트(1) 자리이고, 
    // for문 내용을 보다시피 자식과 큰지 작은지의 비교가 계속되기 때문에
    // i*2 (자식 중 작은애) 가 size(현재 힙의 길이) 값보다는 작아야 비교하는 의미가 있다
    for(int i = 1 ; i*2 <= size ;){
      // 지금 위치에서 부모자격이 있다면 반복문을 빠져나온다
      if(heap[i] > heap[i*2] && heap[i] > heap[i*2+1]){
        break;
      } // 자식 둘 중 더 큰 자식과 위치를 교환한다
      else if( heap[i*2] > heap[i*2+1]){
        int temp = heap[i];
        heap[i] = heap[i*2];
        heap[i*2] = temp;
        i = i*2;
      }
      else{
        int temp = heap[i];
        heap[i] = heap[i*2+1];
        heap[i*2+1] = temp;
        i = i*2+1;
      }
    }
		// 받아뒀던 원래 루트값을 반환한다
    return item;
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());

    int[] heap = new int[t+1];
    int size = 0;

    StringBuilder sb = new StringBuilder();
    while( t-- > 0 ){
      int n = Integer.parseInt(br.readLine());
      // 입력 값이 0 이면 heap에서 최대값을 출력한다
      if( n == 0 ){
        sb.append(deleteHeap(heap, size));
        if(size > 0) size--;
      }else{ // 그 외의 입력값에 대해서는 삽입한다
        insertHeap(heap, size++, n);
      }
    }
  }
}