📢이번 글에서는 자바 언어로 힙 자료구조를 구현하는데 초점을 맞출 것이니, 힙 자료구조에 대한 자세한 내용은 힙(파이썬 버전)을 참고하세요.

우선순위 큐 클래스 사용법

우선순위 큐 마지막 공간에 7을 넣으면

7이 포함된 subtree에서 부모 노드와 값을 비교하고, 자식 노드가 부모 노드보다 값이 작으므로(우선순위가 큼) 서로 스왑을 한다.

자바의 유틸 라이브러리를 사용하면 아래와 같이 간단하게 구현할 수 있다.

💻우선순위 큐

package src;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        pq.offer(10);
        pq.offer(8);
        pq.offer(17);
        pq.offer(25);
        pq.offer(16);
        pq.offer(7);

        for (Integer i : pq) {
            System.out.println(i); // 1 10 7 17 25 16 8
        }
    }

}

• 기본은 우선순위가 낮은 숫자가 부여되고,
  만약 높은 숫자가 우선순위(max heap)가 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 new 인자에 넣으면 된다.
• 컬렉션 타입의 add() 메서드도 있지만, Queue 인터페이스를 그대로 구현한 클래스가 PriorityQueue이므로 메서드의 일관적 사용을 위해 offer(), poll(), peek()를 그대로 사용할 것을 권장한다.
  • offer()는 큐가 가득 찼을 때 예외가 아니라 false를 반환하므로(poll()도 마찬가지), 예외 처리 없이도 안전하게 사용할 수 있다.
    • offer() 내부에는 siftUp()이 구현되어 있고, poll()도 마찬가지로 내부적으로 siftDown()이 구현되어 있다.

📚참고자료
🔗[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리: https://coding-factory.tistory.com/603