[JAVA/알고리즘] 최대 힙 (백준 11279)

 

Java에서 Heap은 PriorityQueue를 활용하여 쉽게 구현할 수 있다. 

 

최대 힙은 root에 최댓값이 최소 힙은 root 최솟값이 저장되어 있는 이진 트리라고 생각하면 된다.

 

기본적으로 Java에서 PriorityQueue는 최소힙으로 구현되어 있다. 

 

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

 

Collections.reverseOrder()을 이용하여 최대 힙으로 구현 가능하다. 

 

 

---

[백준 11279]

간단한 최대 힙 구현 문제이다. 

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));
        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i=0; i<n; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                if(heap.isEmpty()) System.out.println(0);
                else System.out.println(heap.poll());
            }
            else{
                heap.add(x);
            }
        }
    }
}

 

 

 

이 외에도 PrioritiyQueue 정렬을 커스텀할 수 있다. 

https://coding-tomorrow.tistory.com/27

[Java / 알고리즘] 우선순위 큐 (Priority Queue)