[백준][JAVA] 11279 : 최대 힙

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

11279번: 최대 힙

최대 힙(Max Heap)

• 최대 트리는 각 노드의 키 값이(자식 노드가 있다면) 그 자식의 키값보다 크거나 같은(작지 않은) 트리이다.
• 최대 힙은 최대 트리이면서 완전 이진 트리이다.

참고 :  https://juhee-maeng.tistory.com/94

[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
    public static class maxHeap{
        private ArrayList<Integer> heap;
        
        public maxHeap(){
            heap=new ArrayList<>();
            heap.add(1000000);
        }

        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((p*2)<heap.size()){
                int max=heap.get(p*2);
                int maxP=p*2;
                if(((p*2+1)<heap.size())&& max<heap.get(p*2+1)){
                    max = heap.get(p*2+1);
                    maxP=p*2+1;
                }

                if(heap.get(p)>max) break;

                int tmp=heap.get(p);
                heap.set(p, heap.get(maxP));
                heap.set(maxP, tmp);
                p =maxP;
            }
            return deleteItem;
        }
    }

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

        for(int i=0; i<N; i++){
            int val=Integer.parseInt(br.readLine());
            if(val==0) System.out.println(max.delete());
            else max.insert(val);
        }
    }
}