[자료구조2] 백준 11279 최대 힙

11279번: 최대 힙

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

 

# 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 StringBuilder
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // PriorityQueue 를 이용해 최대 힙 구현
        // reverseOrder() == 큰 숫자부터 꺼내짐 == 최대 힙
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 연산의 개수 N
        long n = Long.parseLong(br.readLine());

        for (long i = 0; i < n; i++) {
            String input = br.readLine();

            if (input.equals("0")) {
                // 입력이 0이면 배열에서 가장 큰 값을 출력하고 제거
                // 배열이 비어 있을 경우 0 출력
                if (maxHeap.isEmpty()) {
                    sb.append("0").append("\n");
                } else {
                    sb.append(maxHeap.poll()).append("\n");
                }
            } else {
                // 입력이 0이 아니면 해당 값을 추가
                maxHeap.offer(Long.parseLong(input));
            }
        }

        System.out.println(sb);

        // Reader 버퍼 닫기
        br.close();
   }
}

• 자바에서 힙은 우선순위 큐 (Priority Queue) 자료구조를 사용하면 간단하게 구현할 수 있다.
• 힙 (Heap) : 완전 이진트리 형태로, 최대/최소값을 빠르게 찾아내는데 유용한 자료구조. 중복값을 허용하며 부모-자식 간 정렬은 보장, 형제간의 정렬은 보장하지 않는 반 정렬 상태의 자료구조이다.
• 최소 힙 (Min Heap) : 루트 노드가 최솟값인 힙
• 최대 힙 (Max Heap) : 루트 노드가 최댓값인 힙