[JAVA] 최소힙, 최대힙 사용법 정리(PriorityQueue)

 

요즘 백준에서 data_structures 관련 문제를 풀고있다.

여기는 자료구조인 큐, 스택, 힙 등을 이용하는 문제들이 많기 때문에 큐, 스택, 힙에 대한 사용법을 충분히 숙지해야 문제를 잘 풀 수 있다!

그래서 오늘은 힙 사용법을 정리해보려고 한다.

 

 

 

힙(Heap)이란?

여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진트리

 

• 힙은 여러 개의 값 중 최솟값을 찾거나, 최댓값을 찾을 때 이용된다
• 최솟값을 찾기위한 힙을 최소힙(Min heap)이라고 함
• 최댓값을 찾기위한 힙을 최대힙(Max heap)이라고 함

 

 

힙의 저장방식(최소 힙)

나무위키, 최소힙 예시

• 힙은 완전 이진 트리의 형태를 띈다
• 최소 힙은 부모의 값이 항상 자식보다 작다
• 최대 힙은 부모의 값이 항상 자식보다 크다

 

나무위키, 최소힙 데이터 삭제 방식

• 최소힙에서의 삭제 = 최솟값 뽑기
• 삭제 방식은 루트노드(=최솟값)를 뺀 후, 다시 트리를 구성하는 방식을 사용한다
• 트리높이만큼 타고 내려가기 때문에 시간은 O(logN)이 걸림

 

나무위키, 최소힙 데이터 삽입 방식

• 데이터를 삽입하는 방법은 리프노드 밑에 달고, 부모와 크기를 비교하고 위로 올라가면서 자기 자리를 찾는 방식을 사용한다
• 트리높이만큼 타고 올라가기 때문에 시간은 O(logN)이 걸림

 

 

힙의 시간복잡도(최소힙)

• 데이터 삽입: O(logN)     //N은 트리의 레벨(높이)
• 데이터 삭제(=최솟값 뽑기) : O(logN)

 

 

힙은 어디에 저장할까? 트리를 만드나?

나무위키는 누가 쓰는걸까? 설명 너무 잘함

• 완전 이진트리 특징: 배열로 표현하기 좋음
  • 2를 곱하고 나누고 하면 부모자식을 쉽게 찾을 수 있다
• 이 방식으로 배열에 직접 구현할 수도 있겠지만, 자바에는 컬렉션이라는 게 있다!
• 자바의 PriorityQueue라는 컬렉션을 사용하면 이미 만들어둔 힙을 쉽게 사용가능함 

 

 

PriorityQueue 사용방법

 

최소힙, 최대힙 만들기

//최소힙 만들기
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//최대힙 만들기
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

• PriorityQueue로 힙을 구현함
• 디폴트는 최소힙으로 만들어지고, reverseOrder를 생성자에 넣어주면 최대힙이 만들어짐

 

값 추가

minHeap.add(1);
maxHeap.add(1);

• add하면 내부에서 알아서 정렬됨
• O(logN)

 

최솟값, 최댓값 뽑기

//[1,2,3,4,5] 가 힙에 있다고 가정

int tmp = minHeap.poll(); //1
int tmp2 = minHeap.remove(); //2

• 최소힙의 경우 poll()이나 remove() 를 사용하면 루트노드 값(최솟값)이 나오고, 힙에서 삭제된다
• 재정렬이 필요하니 O(logN)의 시간이 걸림

 

삭제없이 최솟값만 확인하기

int tmp = minHeap.peek();

• 이렇게 하면 minHeap에서 최솟값은 삭제되지 않지만, 최솟값이 뭔지는 알 수 있다
• 루트노드 값만 뽑으면 되니까 O(1)이 걸림

 

 

(중요)iterator로 출력하거나 for문으로 힙을 출력 시 내림차순 혹은 오름차순으로 출력되지 않음

• 내림차순 혹은 오름차순으로 출력하는 방법은 poll을 반복하는 방법밖에 없다

 

 

그외에도

• remove(index) 로 인덱스에 해당하는 값을 삭제할 수도 있음(순서대로 정렬되었다고 생각, index번째로 작은 값)
• clear() 로 priority queue를 비울 수 있다

 

 

백준에서 풀어보는 힙 문제

 

1927 최소 힙 - 실버2

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

1927번: 최소 힙

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    StringBuffer sb = new StringBuffer();

    for (int i =0; i<cnt; i++) {
      int cal = Integer.parseInt(br.readLine());

      if (cal == 0) {
        if (minHeap.isEmpty())
          sb.append(0);
        else
          sb.append(minHeap.poll());
        sb.append("\n");
      } else {
        minHeap.add(cal);
      }
    }

    System.out.println(sb);
  }
}

• (이전 게시글에서도 풀었지만 재탕)

 

 

11279 최대 힙 - 실버2

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

11279번: 최대 힙

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (int i =0; i<cnt; i++) {
      int input = Integer.parseInt(br.readLine());

      if (input == 0) {
        if (maxHeap.isEmpty())
          sb.append("0").append("\n");
        else
          sb.append(maxHeap.poll()).append("\n");
      } else
        maxHeap.add(input);
    }

    System.out.println(sb);
  }
}

 

 

 

 

 

 

이제부턴 많이 풀어보는 게 답이다! 

손에 익을때까지 계속 풀어봐야지

 

 

 

 

참고자료

1. 나무위키, 힙 트리, https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC       
2. PriorityQueue 사용법 블로그, https://crazykim2.tistory.com/575