[Data structure]최대힙/최소힙

자료구조의 핵심 중 하나인 힙(Heap)에 대해서 알아보고, Java에서 어떻게 구현하는지 살펴보고자 한다.

힙(Heap)

• 힙은 최대값 또는 최소값을 빠르게 찾아낼 수 있는 트리형 자료 구조이다.

• 완전 이진트리의 일종이며, 모든 부모 도느 값이 자식 노드들의 값과 일정한 대소 관계를가지게 되는 규칙을 갖는다.

• 하지만 자식노드간은 상관관계 없음 !

• 완전이진트리와는 다르게 중복값을 허용한다.

• 삽입/ 삭제는 트리구조이기 때문에 O(longN)으로 매우 빠르다.

• 최대 최소값은 트리 가장 상단의 노드이기 때문에 O(1)만에 찾을 수 있다.

• 자바에서 구현하기 위해서는 우선순위큐 로 힙을 구현한다. 이는 배열과 리스트보다 효율적이다. !

• 힙은 👉 최대힙/ 최소힙 으로 나눠진다.

  • 최대힙: 부모노드 값이 자식노드의 값보다 큰 경우
  • 최소힙: 부모노드 값이 자식노드의 값보다 작은 경우
    • 이것을 통해 여러 값 중에서 최소값이나 최대 값을 빨리 찾을 때 유용하다.

• 힙의 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용되지 않는다.

  1번째 인덱스부터 시작하며, 해당 인덱스의 자식 노드는 *2 , *2 +1로 나타낼 수 있다.

  즉, 1번의 자식 노드는 2번, 3번 /2번의 자식노드는 4번, 5번이 된다.

문제

• 최소힙: https://www.acmicpc.net/problem/1927

  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Comparator;
  import java.util.PriorityQueue;
    
  public class Main {
      public static void main(String[] args) throws Exception {
          BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    
          int size = Integer.parseInt(bufferedReader.readLine());
          PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  return o1-o2;
              }
          });
    
          while (size -- > 0){
              int num = Integer.parseInt(bufferedReader.readLine());
              if (num == 0){
                  if (queue.isEmpty()) System.out.println(0);
                  else System.out.println(queue.poll());
              }else{
                  queue.add(num);
              }
          }
    
    
      }
  }
  

• 최대힙: https://www.acmicpc.net/problem/11279

  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Comparator;
  import java.util.PriorityQueue;
    
  public class Main {
      public static void main(String[] args) throws Exception {
          BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    
          int size = Integer.parseInt(bufferedReader.readLine());
          PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  return o2-o1;
              }
          });
    
          while (size -- > 0){
              int num = Integer.parseInt(bufferedReader.readLine());
              if (num == 0){
                  if (queue.isEmpty()) System.out.println(0);
                  else System.out.println(queue.poll());
              }else{
                  queue.add(num);
              }
          }
      }
  }