[알고리즘] 백준 1927 최소 힙

1927번: 최소 힙

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

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

/**
 *packageName    : org.example.알고리즘.최소힙
 * fileName       : Main
 * author         : ipeac
 * date           : 2024-02-12
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2024-02-12        ipeac       최초 생성
 */
public class Main {
	static int N;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			PriorityQueue<Integer> queue = new PriorityQueue<>();
			N = Integer.parseInt(br.readLine());

			for (int i = 0; i < N; i++) {
				int x = Integer.parseInt(br.readLine());
				if (x == 0) {
					if (queue.isEmpty()) {
						System.out.println(0);
					} else {
						System.out.println(queue.poll());
					}
				} else {
					queue.add(x);
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

• 겁나 단순한 문제다

  PriorityQueue 는 우선순위 큐를 구현한다.

  • 각 요소가 우선순위를 가지며, 우선 순위가 높은 요소부터 먼저 제거된다.
  • 해당 큐는 기본적으로 최소 힙(Min Heap) 을 사용하여 구현되어 있다.

  최소 힙?

  • 완전 이진 트리의 한 종류다
    • 완전 이진 트리는
      • 모든 부모 노드가 자식노드보다 작거나 같은 값을 가지는 트리이다.
      • 그림으로 간단히 설명하면

        

        • 주요 연산
          • 삽입(offer / add)
            • 새 요소를 힙에 추가하는 경우, 힙의 마지막 요소를 삽입 후,
            • 부모 노드와 비교하여 힙 속성을 만족할 때까지 위로 올린다
            • (Up Heap 연산)
          • 삭제(poll / remove)
            • 힙에서 가장 작은 요소(루트)를 제거할 때, 힙의 마지막 요소를 루트로 이동시킨 후,
            • 자식 노드와 비교하여 힙 속성을 만족할 때까지 아래로 내립니다(Down-Heap 연산).

              

          • 조회(peek)
            • 루트를 항상 반환한다.

Uploaded by N2T