[백준][JAVA] 1874 : 최소 힙

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

1927번: 최소 힙

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
    public static class minHeap{
        private ArrayList<Integer> heap;
        
        public minHeap(){
            heap=new ArrayList<>();
            heap.add(0);
        }
        
        public void insert(int val){
            heap.add(val);
            int p=heap.size()-1;

            while(p>1 && heap.get(p/2)>heap.get(p)) {
                int temp = heap.get(p / 2);
                heap.set(p / 2, heap.get(p));
                heap.set(p, temp);
                p /= 2;
            }
        }
        
        public int delete(){
            if(heap.size()-1<1) return 0;
            
            int deleteItem = heap.get(1);
            
            heap.set(1, heap.get(heap.size()-1));
            heap.remove(heap.size()-1);

            int p=1;
            
            while((pos*2)<heap.size()){
                int min=heap.get(p*2);
                int minP=p*2;
                
                if(((p*2+1)<heap.size())&& min>heap.get(p*2+1)){
                    min = heap.get(p*2+1);
                    minP=p*2+1;
                }
                
                if(heap.get(p)<min) break;
                
                int tmp=heap.get(p);
                heap.set(p, heap.get(minP));
                heap.set(minP, tmp);
                pos=minP;
            }
            return deleteItem;
        }
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        minHeap mh=new minHeap();
        
        for(int i=0; i<N; i++){
            int val=Integer.parseInt(br.readLine());
            if(val==0) System.out.println(mh.delete());
            else mh.insert(val);
        }
    }
}