[Java] 11279번. 최대 힙 (# Heap)

문제링크 : https://www.acmicpc.net/problem/11279

설명은 최소 힙 포스팅 참고.
https://velog.io/@osh8242/BOJ-1927

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        MaxHeap heap = new MaxHeap();
        int n = Integer.parseInt(br.readLine());
        for(int test = 1 ; test <= n ; test++){
            int command = Integer.parseInt(br.readLine());
            if(command==0){
                sb.append(heap.poll()+"\n");
            } else {
                heap.insert(command);
            }
        }
        System.out.println(sb.toString());
    }

}

class MaxHeap {
    private ArrayList<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
        heap.add(0);
    }

    public void insert(int num) {
        heap.add(num);
        int i = heap.size() - 1;
        while (i > 1 && heap.get(i / 2) < num) {
            heap.set(i, heap.get(i / 2));
            heap.set(i / 2, num);
            i /= 2;
        }
    }

    public int poll() {
        if(heap.size()==1) return 0; // 값이 없으면 return 0;
        int max = heap.get(1); // index 1이 최대값이므로 max에 get(1);
        heap.set(1, heap.get(heap.size()-1)); // 맨 뒤 값을 맨 앞으로 복사해옴
        heap.remove(heap.size()-1); // 맨 뒤 값 제거
        int i = 1; // 정렬을 시작할 시작 index
        while(2*i < heap.size()){ // 왼쪽 자식노드가 존재한다면
            int cVal = heap.get(2*i);
            int cIndex = 2*i;
            
            // 오른쪽 자식노드가 존재하는데 오른쪽 자식노드 값이 왼쪽 자식노드 값보다 더 크다면
            if(2*i+1 < heap.size() && heap.get(2*i+1) > cVal){ 
                cVal = heap.get(2*i+1);
                cIndex = 2*i+1;
            }
            
            //자식노드보다 부모노드가 크다면 정렬 종료 break;
            if(heap.get(i) >= cVal) break;
            
            //자식노드와 부모노드 값 바꾸기
            heap.set(cIndex, heap.get(i));
            heap.set(i, cVal);
            i = cIndex; // 탐색위치를 자식노드로 옮겨감
        }
        return max; //최대값 반환
    }
}