우선순위 큐?

특정 정렬 기준에 따라 정렬되어 존재하게되는 큐이며, FIFO가 아닌 우선 순위에 따라 입출력이 결정된다.

자바에서는 다음과 같이 사용된다.

• 힙은 이진트리 형식으로 되어있다.
• 보통 최소 Heap, 최대 Heap 으로 표현된다
• 최소 힙은 부모 노드가 가장 작은 것, 최대 힙은 부모 노드가 가장 큰 수로 시작한다.
• 최소 힙에서 자식 노드는 부모보다 작거나 같아야 한다
• 최대 힙에서 자식 노드는 부모보다 크거나 같아야 한다

public class PriorityQueuePrac {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(10, Collections.reverseOrder());

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 요소 추가
        maxHeap.add(5);
        maxHeap.add(2);
        maxHeap.add(10);
        maxHeap.add(3);

        minHeap.add(5);
        minHeap.add(2);
        minHeap.add(10);
        minHeap.add(3);

        // 요소 삭제
        while (!maxHeap.isEmpty()) {
            int maxHeapElement = maxHeap.poll();
            System.out.println(maxHeapElement + "maxHeap!!");
        }

        while (!minHeap.isEmpty()){
            int minHeapElement = minHeap.poll();
            System.out.println(minHeapElement + "minHeap!!");
        }
    }

---

Heap 을 사용하는 문제 (문제 링크)

public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(scoville.length);
        int answer = 0;

        for (int i : scoville) {
            pq.add(i);
        }

        while (pq.peek() < K){
            if (pq.size() == 1){
                return -1;
            }

            int min1 = pq.poll();
            int min2 = pq.poll();

            int newInt = min1 + min2 *2;
            pq.add(newInt);
            answer++;
        }

        return answer;
    }

우선순위 큐를 사용해서 항상 작은 순서로 정렬되어 있는 Queue를 이용한다.

가장 작은 놈 두개를 poll해서 뽑아온 후 합쳐서 다시 add 하면 또 다시 최소 요소 순서대로 정렬된다.