📝문제

힙(Heap)이란?

배열 속에서 최대값과 최솟값을 쉽게 찾아내기 위해서 구현한 자료구조이다.
우선순위 큐를 위해서 만들어진 것으로, 배열과 연결리스트로 구현하는 것보다 효율적이다.
힙은 이진트리형태를 가지며, 가장 중요한 특징 중 한 가지는 부모와 자식간의 대소 규칙이 명확하다는 것이다.

최대 힙의 경우 : 부모 노드의 값 > 자식 노드의 값
최소 힙의 경우 : 부모 노드의 값 < 자식 노드의 값

새로운 값이 추가되는 경우 : 가장 마지막 노드에 값을 추가한 후, 부모 노드와 값을 비교하면서 둘의 위치를 교체한다.
값을 제거하는 경우 : 루트 노드의 값이 제거되고, 마지막 노드의 값을 루트 노드로 가져온 후, 자식 노드들 중 더 적은(혹은 큰) 값과 교체한다.

최댓값을 찾아내 출력하는 문제라서 우선순위 큐가 바로 떠올랐고, 적용하여 풀었다.

📌코드

package Baekjoon;

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

public class BOJ11279 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));//내림차순
        for(int i = 0; i < n; i++){
            int input = Integer.parseInt(br.readLine());
            if(input == 0){
                if(pq.isEmpty()) sb.append(0).append("\n");
                else sb.append(pq.poll()).append("\n");
            } else {
                pq.add(input);
            }
        }
        System.out.println(sb);

    }
}