우선 순위 큐와 힙

Priority queue(우선순위 큐) - > ADT

• 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

우선순위 큐 주요 동작

• insert

• delete

• peek

Heap

• 힙은 주로 이진 트리(binary tree) 기반으로 구현

• 트리 부모-자녀처럼 계층적인 형태를 가지는 구조

• 이진 트리 -> 자녀가 최대 두 개인 구조

• 힙은 주로 이진 트리(binaray tree) 기반으로 구현

힙은 max heap과 min heap이 있다 -> 우선순위 큐의 구현

max heap : 부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 크거나 같은 트리

min heap : 부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 작거나 같은 트리

힙 주요 동작

• insert

• delete

• peek

힙 동작 메커니즘

ex) max heap

insert 작업은 맨 마지막 위치에 추가하고, 자신의 부모 노드와 비교해서 큰지 작은 지 비교 후 스위칭해나가면 된다.

delete 작업

delete는 트리에서 가장 큰 크기의 값, 최상단 노드(root node)를 제거하는 것이다. 이때 비어 있는 최상단 노드의 위치에 가장 마지막 노드를 넣어준다. 이제 자녀 노드 둘 중 더 큰 값과 자리를 바꿔준다. 자녀 노드(들)보다 더 클 때 스위칭을 멈춘다.

✅ Max Heap의 핵심 구조

✔ 자료구조: 배열(Array)

• 힙은 완전 이진 트리(Complete Binary Tree) 구조

• 배열을 사용하면 트리 구조를 포인터 없이 효율적으로 저장 가능

✔ 저장 방식 (0-based 인덱스 기준):

노드 위치	인덱스 계산 방법
부모 노드	i
왼쪽 자식	2 * i + 1
오른쪽 자식	2 * i + 2
부모	(i - 1) / 2 (정수 나눗셈)

      50
     /  \
   30    40
  / \    /
10  20  35

int[] heap = {50, 30, 40, 10, 20, 35};

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap

• 내부적으로 Object[] queue라는 배열을 사용

• 실제 삽입/삭제는 siftUp, siftDown 같은 heapify 함수로 유지

• 정렬 조건은 Comparator 또는 Comparable 기반

힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐(priority queue)의 구현체가 된다.

Priority queue = ADT

Heap = data structure

우선 순위 큐와 힙의 사용 예시

• 프로세스 스케줄링(process scheduling)

heap sort(힙 정렬)

✅ 1. 힙 기반 우선순위 큐 (✔ 자바의 기본 방식)

📌 구조: Min Heap / Max Heap (이진 힙)

PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min Heap

연산	시간 복잡도
삽입	O(log n)
꺼내기 (poll)	O(log n)
최솟값/최댓값 조회 (peek)	O(1)

• ✅ 메모리 적고 빠름

• ❗ 정렬된 순서 유지 안 함

• ✔ 대량 데이터 처리에 매우 효율적

---

✅ 2. TreeMap 기반 우선순위 큐 (✔ 완전 정렬 유지)

📌 구조: TreeMap<우선순위, Queue<값들>>

TreeMap<Integer, Queue<String>> pq = new TreeMap<>();

• 우선순위(key)로 정렬되고,

• 같은 우선순위 값은 큐에 저장

예제

public class MaxPriorityQueue<K extends Comparable<K>, V> {
    private final TreeMap<K, Queue<V>> map = new TreeMap<> (Collections.reverseOrder()); // Max Priority
    private int size = 0;
    
    public void enqueue(K priority, V value) {
        map.computeIfAbsent(Priority, k -> new LinkedList<>()).add(value);
        size++;
    }

연산	시간 복잡도
삽입	O(log n)
삭제	O(log n)
전체 정렬된 순회	✅ 가능

• ✅ 전체를 정렬된 순서로 꺼낼 수 있음

• ❗ 힙보다 메모리 사용 많음

• ❗ 속도도 힙보다 약간 느림

• ✔ 멀티 우선순위 처리 필요 시 유리