Intro::
우선순위 큐와 힙에 대한 정리입니다.
우선순위 큐
•
정의: 가장 높은 우선순위 항목을 먼저 꺼내는 추상 자료구조입니다.
•
동작: 삽입(insert) 시 우선순위를 함께 지정하고, 삭제(remove) 시 우선순위가 가장 높은 항목을 반환합니다.
힙
•
정의: 완전 이진 트리 형태로 구현한 배열 기반 자료구조입니다.
•
동작: 부모 노드의 값이 자식 노드의 값보다 크거나(최대 힙) 작도록(최소 힙) 유지합니다. 이 성질 덕분에 루트(root) 노드에 최대값 또는 최소값이 위치합니다.
차이점
구분 | 우선순위 큐 | 힙 |
자료구조 유형 | 추상(어떤 방식으로든 구현 가능) | 구체적(완전 이진 트리 배열 구현) |
인터페이스 | offer, poll, peek 등 제공 | 배열과 인덱스 연산으로 직접 구현 |
시간 복잡도 | 일반적으로 O(log n) (힙 기반 구현) | 삽입·삭제·최댓값/최솟값 조회 O(log n) |
사용 예시 | 작업 스케줄링, 다익스트라 최단경로 | 힙 정렬, 우선순위 큐 내부 구현 |
요약: 우선순위 큐는 ‘무엇을 할 수 있는지’를, 힙은 ‘어떻게 구현했는지’를 말합니다.
우선순위 큐 사용 예시
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 숫자가 작을수록 우선순위가 높음(최소 힙)
PriorityQueue<String> pq = new PriorityQueue<>(
(a, b) -> Integer.compare(getPriority(a), getPriority(b))
);
pq.offer("작업A: 우선순위 2"); // 우선순위 2
pq.offer("작업B: 우선순위 1"); // 우선순위 1
pq.offer("작업C: 우선순위 3"); // 우선순위 3
// 우선순위가 가장 높은 항목(숫자 1)부터 꺼냄
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
private static int getPriority(String task) {
// 문자열 끝 숫자로 우선순위를 판단
return Integer.parseInt(task.substring(task.length() - 1));
}
}
Java
복사
•
PriorityQueue 클래스는 내부적으로 힙(완전 이진 트리 배열)을 사용해 구현됩니다.
최소 힙 직접 구현 예시
public class MinHeap {
private int[] heap;
private int size;
public MinHeap(int capacity) {
heap = new int[capacity + 1]; // 1번 인덱스부터 사용
size = 0;
}
// 삽입
public void add(int value) {
heap[++size] = value;
int cur = size;
while (cur > 1 && heap[cur] < heap[cur / 2]) {
swap(cur, cur / 2);
cur /= 2;
}
}
// 삭제(최솟값 반환)
public int poll() {
if (size == 0) return -1;
int min = heap[1];
heap[1] = heap[size--];
heapify(1);
return min;
}
private void heapify(int idx) {
int smallest = idx;
int left = idx * 2;
int right = idx * 2 + 1;
if (left <= size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right <= size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != idx) {
swap(idx, smallest);
heapify(smallest);
}
}
private void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
public static void main(String[] args) {
MinHeap heap = new MinHeap(10);
heap.add(5);
heap.add(2);
heap.add(8);
System.out.println(heap.poll()); // 2
System.out.println(heap.poll()); // 5
}
}
Java
복사
•
배열 인덱스 연산을 통해 부모·자식 관계를 유지하며 힙 속성을 관리합니다.
