자료구조 시리즈 10편

힙(Heap)과 우선순위 큐(Priority Queue) 완전 이해하기

이전 글에서는 그래프(Graph)에 대해 알아봤습니다.
이번에는 우선순위가 높은 데이터를 빠르게 꺼내는 자료구조, 힙(Heap) 과 우선순위 큐(Priority Queue) 를 자세히 정리해봅니다.

---

1. 힙(Heap)이란?

힙은 완전 이진 트리 형태를 가지면서 특정 규칙을 만족하는 자료구조입니다.

• 완전 이진 트리: 모든 레벨이 꽉 차고, 마지막 레벨만 왼쪽부터 채워짐
• 힙 조건:
  • 최소 힙(Min Heap): 부모 노드 ≤ 자식 노드
  • 최대 힙(Max Heap): 부모 노드 ≥ 자식 노드

---

2. 힙의 특징

항목 설명

삽입 속도	O(log n)
삭제(최대/최소값 꺼내기) 속도	O(log n)
정렬된 순서 보장	X (최대/최소만 빠르게 접근)
사용 용도	우선순위 큐, 정렬(Heap Sort)

---

3. 우선순위 큐(Priority Queue)란?

우선순위가 높은 데이터를 먼저 꺼낼 수 있도록 힙으로 구현된 큐입니다.

• 일반 큐는 먼저 들어온 데이터가 먼저 나옴 (FIFO)
• 우선순위 큐는 우선순위 높은 데이터가 먼저 나옴
• 힙을 기반으로 구현하여 효율적으로 동작

---

4. 힙 기본 구현 예시 (C# 기준)

.NET 6 이상에서는 PriorityQueue 클래스를 사용할 수 있습니다.

 PriorityQueue 선언과 사용

using System.Collections.Generic;

PriorityQueue<string, int> pq = new PriorityQueue<string, int>();

// 요소 추가 (데이터, 우선순위)
pq.Enqueue("Task1", 3);
pq.Enqueue("Task2", 1);
pq.Enqueue("Task3", 2);

// 가장 우선순위 높은 요소 꺼내기
string task = pq.Dequeue();
Console.WriteLine(task); // "Task2" 출력 (우선순위 1이 가장 높음)

 수동 힙 구조 예시 (배열 기반)

List<int> heap = new List<int>();

void Insert(int value)
{
    heap.Add(value);
    int i = heap.Count - 1;

    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) break;

        (heap[parent], heap[i]) = (heap[i], heap[parent]);
        i = parent;
    }
}

 

 

5. 실생활 예시로 이해하기

• 힙 = 대기열에서 가장 급한 환자부터 치료하는 응급실 시스템
• 힙 = 티켓 예매 사이트에서 VIP 고객을 먼저 처리하는 구조

---

6. 힙과 우선순위 큐의 활용 사례

사용 예시 설명

CPU 스케줄링	우선순위 높은 프로세스 먼저 실행
네트워크 패킷 처리	긴급 데이터 먼저 전송
다익스트라 최단 경로 알고리즘	최소 비용 정점 먼저 선택

---

이번 글에서는 힙(Heap) 과 우선순위 큐(Priority Queue) 의 개념, 특징, C# 코드 사용법을 정리했습니다.

• 힙은 최대/최소값을 빠르게 꺼낼 수 있는 완전 이진 트리
• 우선순위 큐는 힙을 사용해 우선순위 높은 데이터부터 처리
• 시스템 스케줄링, 최단 경로 탐색 등에서 광범위하게 사용