[백준] 11279번 : 최대 힙

최대 힙

---

풀이 방법

이번엔 자료 구조인 최대 힙을 구현하는 문제였다.

우선 먼저 알고 있어야 할 지식으로

힙 (Heap)

• 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다.
• 최대 값, 최소 값 찾기에 효과적이다.
• 우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다.
• 부모는 자식보다 우선순위가 더 높은 데이터가 배치된다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

힙(heap)의 종류

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  key(부모노드 >= key(자식노드)

최소 힙(min heap)

• 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
  key(부모노드) <= key(자식노드)

우선순위 큐 (PriorityQueue)

일반 큐처럼 들어온 순서대로 나가는 것이 아닌 우선순위를 결정해 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조이다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적인데, Java 에서는 기본적으로 제공하고 있다.

Java에서는 편하게 제공하는 기능이지만, 어떻게 동작하는지는 알고 있자!

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i=0;i<n;i++){
            int x = Integer.parseInt(br.readLine());
            if(x>0){
                maxHeap.add(x);
            }
            else if(x==0){
                if(maxHeap.isEmpty()){
                    sb.append(0).append("\n");
                }
                else{
                    int max = maxHeap.remove();
                    sb.append(max).append("\n");
                }
            }
        }

        System.out.println(sb);
    }
}

---

참고 블로그

힙에 대한 정보 정리 (Heap 삽입,삭제 동작이 가물가물하면 다시 보자)

잘 정리해주셔서 감사합니다!!
https://velog.io/@holicme7/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap-ktk49na9c3