힙(Heap): 우선순위 기반 데이터 구조의 개념과 활용

🔹 힙이란?

1. 힙(Heap)의 정의

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 데이터 구조로, 부모 노드가 특정 우선순위 조건을 만족하는 구조입니다. 힙은 우선순위 큐(Priority Queue) 구현, 스케줄링, 힙 정렬 등에 활용됩니다.

✅ 힙의 주요 특징:

• 완전 이진 트리(Complete Binary Tree) 형태를 가짐
• 부모 노드가 항상 특정 우선순위를 유지
• 삽입 및 삭제 연산이 O(log n) 시간 복잡도를 가짐
• 우선순위 큐(Priority Queue)에서 활용됨

📌 힙은 최댓값 또는 최솟값을 빠르게 추출하는 데 최적화된 자료구조입니다.

---

🔹 힙의 주요 유형

1. 최대 힙(Max Heap)

✅ 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 힙

✔️ 최대 힙의 예제:

       50
      /  \
    30    40
   /  \   /  \
  10   5 20   25

📌 최대 힙에서는 항상 루트 노드가 가장 큰 값을 가집니다.

2. 최소 힙(Min Heap)

✅ 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 힙

✔️ 최소 힙의 예제:

       10
      /  \
    30    40
   /  \   /  \
  50   35 45   60

📌 최소 힙에서는 항상 루트 노드가 가장 작은 값을 가집니다.

---

🔹 힙의 주요 연산

1. 삽입(Insert) - O(log n)

✅ 힙에 새로운 요소를 추가하는 연산 (삽입 후 힙 성질 유지)

✔️ 최대 힙 삽입 연산 예제 (Python):

import heapq
heap = []
heapq.heappush(heap, -50)  # 최대 힙을 만들기 위해 음수로 변환
heapq.heappush(heap, -30)
heapq.heappush(heap, -40)
print([-x for x in heap])  # 출력: [50, 30, 40]

📌 Python의 heapq 모듈은 기본적으로 최소 힙을 제공하므로, 최대 힙을 구현하려면 음수를 이용해야 합니다.

2. 삭제(Remove) - O(log n)

✅ 루트 노드(최댓값 또는 최솟값)를 제거하고, 힙 구조를 재정렬하는 연산

✔️ 최소 힙 삭제 연산 예제 (Python):

heapq.heappop(heap)  # 최소값 제거
print(heap)

📌 삭제 연산 후에도 힙의 성질을 유지하기 위해 자동으로 재정렬됩니다.

3. 힙 변환(Heapify) - O(n)

✅ 주어진 리스트를 힙 구조로 변환하는 연산

✔️ Heapify 예제 (Python):

arr = [40, 10, 30, 50, 20]
heapq.heapify(arr)
print(arr)  # 출력: [10, 20, 30, 50, 40] (최소 힙 형태로 정렬됨)

📌 heapify() 연산을 수행하면 주어진 리스트가 힙 속성을 만족하도록 변환됩니다.

---

🔹 힙의 활용 사례

1. 우선순위 큐(Priority Queue)

✅ 우선순위를 기준으로 작업을 처리해야 하는 경우 사용

✔️ 우선순위 큐 예제 (Python):

import heapq
pq = []
heapq.heappush(pq, (1, "Low Priority Task"))
heapq.heappush(pq, (0, "High Priority Task"))
heapq.heappush(pq, (2, "Medium Priority Task"))
print(heapq.heappop(pq))  # 출력: (0, 'High Priority Task')

📌 우선순위가 높은 작업이 먼저 처리됩니다.

2. 힙 정렬(Heap Sort)

✅ 힙을 이용한 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가짐

✔️ 힙 정렬 예제 (Python):

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

arr = [40, 10, 30, 50, 20]
print(heap_sort(arr))  # 출력: [10, 20, 30, 40, 50]

📌 힙 정렬은 불안정 정렬이지만, 최악의 경우에도 O(n log n)의 성능을 유지합니다.

3. 최단 경로 알고리즘(Dijkstra's Algorithm)

✅ 그래프에서 최단 경로를 찾는 데 활용됨

✔️ 다익스트라 알고리즘 예제 (Python):

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))

📌 다익스트라 알고리즘은 네트워크 경로 탐색 및 내비게이션 시스템에서 널리 사용됩니다.

---

📌 결론

✅ 힙(Heap)은 우선순위 기반의 데이터를 효율적으로 처리하는 완전 이진 트리 구조입니다.
✅ 최대 힙과 최소 힙의 개념을 활용하여 최댓값 및 최솟값을 빠르게 검색할 수 있습니다.
✅ 힙은 우선순위 큐, 힙 정렬, 다익스트라 알고리즘 등 다양한 분야에서 사용됩니다.
✅ Python에서는 heapq 모듈을 활용하여 간편하게 힙을 구현할 수 있습니다.