백준 1927번: 최소 힙

https://www.acmicpc.net/problem/1927

배열에 가장 작은 수를 출력하고 삭제하는 연산과 배열에 자연수 x를 추가하는 최소 힙을 구현하는 문제이다.

 

힙은 데이터의 입출력마다 그 크기를 동적으로 변화시켜주는 ArrayList로 구현한다.

데이터의 입력은 일단 마지막에 추가를 하고, 그 뒤에 추가한 노드가 부모노드를 가지고 있다면

추가한 노드가 홀수인지, 짝수인지 확인하고 그것에 맞춰 부모노드랑 크기를 비교해서

더 작다면 부모노드와 위치를 바꿔준다.

그렇게 새로 추가한 노드가 더이상 위치를 바꾸지 않는 지점 혹은 index 0이 될 때 까지 반복해준다.

 

데이터의 출력은 가장 작은 수를 출력하게 하므로 index 0을 출력한다.

그 뒤에 index 0에 마지막 노드를 넣고, 마지막 노드는 삭제해서 크기를 조절한다.

그 뒤로 index 0부터 시작해서 좌우 자식 노드들과 비교를 하면서 제자리를 찾도록 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
  static ArrayList<Integer> heap = new ArrayList<>();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    for (int n = 0; n < N; n++) {
      int x = Integer.parseInt(br.readLine());
      if (x == 0) {
        if ( heap.isEmpty() ) sb.append("0\n");
        else sb.append(del()  + "\n");
      }
      else {
        insert(x);
      }
    }
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(sb + "");
    bw.flush();
    bw.close();
  }

  static int swap(int a, int b) {
    int temp = heap.get(a);
    heap.set(a, heap.get(b));
    heap.set(b, temp);
    return a;
  }

  static void insert(int x) {
    heap.add(x);
    int addNode = heap.size() - 1;

    while(addNode != 0) {
      if ( (addNode-1)%2 == 0 ) { //홀수노드
        if ( heap.get( (addNode-1)/2 ) > x )
          addNode = swap((addNode-1)/2, addNode);
        else break;
      }
      else {  //짝수노드
        if ( heap.get( (addNode-2)/2 ) > x )
          addNode = swap((addNode-2)/2, addNode);
        else break;
      }
    }

  }

  static int del() {
    int root = heap.get(0);
    heap.set(0, heap.get(heap.size() - 1));
    heap.remove(heap.size() - 1);
    int node = 0;
    while (2*node + 1 < heap.size()) {
      int leftNode = 2*node + 1;
      int rightNode = 2*node + 2;
      if (rightNode < heap.size())
        leftNode = (heap.get(leftNode) < heap.get(rightNode)) ? leftNode : rightNode;

      if (heap.get(node) > heap.get(leftNode)) {
        node = swap(leftNode, node);
      }
      else break;
    }
    return root;
  }
}