Baekjoon | Q.11279 - 최대 힙

11279번: 최대 힙

 최대 힙을 구현하는 문제이다.

 

 직접 최대 힙을 구현해서 풀어보는 방법과 우선순위 큐도 힙의 자료구조를 가지고 있으므로 자바에 이미 구현되어있는 PriorityQueue를 이용하여 푸는 방법이 있다. 공부를 위해 직접 구현해보는 방향으로 문제를 풀어보았다.

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static class MyMaxHeap {
    private ArrayList<Integer> heap;

    // Constructor
    public MyMaxHeap() {
      heap = new ArrayList<>();
      heap.add(-1); // 인덱스를 1부터 시작하기 위함.
    }

    // 위치 교환 메서드
    private void swap(int i1, int i2) {
      int temp = heap.get(i1);
      heap.set(i1, heap.get(i2));
      heap.set(i2, temp);
    }

    public void insert(int node) {
      heap.add(node);
      int p = heap.size() - 1;  // 노드의 현재 위치를 표시할 포인터

      // 노드의 위치가 최상위가 되거나
      // 부모 노드의 값이 더 클 때 까지 교환작업 진행
      while(p > 1 && heap.get(p/2) < heap.get(p)) {
        swap(p/2, p); // 교환
        p = p / 2;  // 포인터 이동
      }
    }

    public int delete() {
      if(heap.size() == 1) {  // 힙이 비어있을 경우
        return 0;
      }

      int deletedNode = heap.get(1);
      heap.set(1, heap.get(heap.size()-1)); // 루트 노드의 값을 마지막 노드의 값으로 변경
      heap.remove(heap.size()-1); // 마지막 노드 삭제
      int p = 1;  // 노드의 현재 위치

      // 자식노드가 있을 때까지 반복
      while(p * 2 < heap.size()) {
        // 오른쪽 자식이 없을 경우를 생각해주어야함... 자꾸 p*2+1 인덱스 예외뜸...
        int max_p = p * 2;  // 왼쪽 오른쪽 중 더 큰 값을 가진 노드의 인덱스를 저장할 변수
        if(p * 2 + 1 < heap.size()) { // 오른쪽 자식이 있을 경우
          // 자식 노드 중 더 큰 노드와 교환한다.
          if(heap.get(p*2) < heap.get(p*2+1)) {
            max_p = p*2 + 1;
          }
        }

        if(heap.get(p) > heap.get(max_p)) { // 부모가 자식보다 값이 더 크다면 반복문 탈출
          break;
        }else {
          swap(p, max_p); // 아니라면 값 교환
          p = max_p;  // 포인터 변경
        }
      }

      return deletedNode;
      
    }
  
    
  }
  
  public static void main(String[] args) {
    StringBuilder sb = new StringBuilder();
    Scanner sc = new Scanner(System.in);
    int tc = sc.nextInt();

    MyMaxHeap heap = new MyMaxHeap();
    
    for (int i = 0; i < tc; i++) {
      int input = sc.nextInt();
      if(input > 0) {
        heap.insert(input);
      }else if(input == 0) {
        sb.append(heap.delete() + "\n");
      }
    }

    System.out.println(sb.toString());
    sc.close();
  }
}

 

 ArrayList로 힙을 구현해보았다. 처음에 delete() 메소드를 구현하다가 자꾸만 p * 2 + 1에서 ArrayOutOfBoundsException이 나타났다..... 오른쪽 자식 노드가 없을 경우였다. 풀이에는 조건 분기를 통해 해결해주었다. ArrayList말고 처음부터 배열로 구현하여 Max size를 정해두는 방법으로도 해결할 수 있을 듯 싶다.