힙 (Heap)

힙은 우선순위 큐를 위해 만들어진 자료구조다.

🧐우선순위 큐 (Priority Queue)

•  우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

---

📌Heap이란?

 

Heap은 기본적으로 최대 힙 (Max Heap)과 최소 힙 (Min Heap)으로 나눌 수 있습니다.

• 최대 힙 (Max Heap): 부모 노드는 자식 노드들보다 크거나 같은 값을 가집니다. 즉, 루트 노드에는 가장 큰 값이 위치합니다.
• 최소 힙 (Min Heap): 부모 노드는 자식 노드들보다 작거나 같은 값을 가집니다. 즉, 루트 노드에는 가장 작은 값이 위치합니다.

❗Heap의 특징

1. 완전 이진 트리: Heap은 노드들이 왼쪽에서 오른쪽으로 빈틈없이 채워지는 완전 이진 트리 구조를 가집니다.
2. 효율적인 연산: 힙에서는 삽입, 삭제 등의 연산이 발생할 때도 트리 구조를 유지하는데, 이를 위해 시간 복잡도 O(log n) 내에서 연산을 수행합니다.
3. 빠른 최대/최소 값 탐색: 트리의 루트에 항상 최대값(최대 힙)이나 최소값(최소 힙)이 존재하므로, 이러한 값들을 빠르게 탐색할 수 있습니다.

💻Heap의 주요 연산

1. 삽입 (Insert): 새로 삽입된 요소는 완전 이진 트리의 특성상 트리의 마지막 노드에 추가됩니다. 이후 부모 노드와 비교하며 자리를 교환하는 방식으로 힙의 조건을 만족시킵니다.

   

2. 삭제 (Delete): 루트 노드(최대값 혹은 최소값)를 삭제한 후, 트리의 마지막 노드를 루트 자리에 옮깁니다. 이후 자식 노드들과 비교하며 자리를 교환하여 힙의 구조를 다시 정렬합니다.

   

3. 힙 정렬 (Heap Sort): 힙을 이용하면 배열을 정렬할 수 있습니다. 힙을 통해 최대값 또는 최소값을 지속적으로 추출하고, 추출된 값을 배열에 넣어 정렬을 수행합니다. 이 과정의 시간 복잡도는 O(n log n)입니다.

---

🛠️구현 예시

Python에서는 heapq 모듈을 제공하여 간단하게 최소 힙을 구현할 수 있습니다.

• 최소힙 현

import heapq

# 최소 힙 생성
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)

print("Min Heap:", min_heap)  # [1, 3, 5]

# 최소값을 추출 (삭제)
min_value = heapq.heappop(min_heap)
print("Heap after pop:", min_heap)     # [3, 5]

 

• 최대힙 구현

Python의 heapq 모듈은 기본적으로 최소 힙을 지원하므로, 최대 힙을 구현하려면 음수 값을 넣어주는 방식으로 처리합니다. 힙에 값을 넣을 때 음수로 변환하고, 꺼낼 때 다시 양수로 변환하는 방식입니다.

# 최대 힙 생성 (음수 값을 이용하여 최대 힙으로 구현)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)

print("Max Heap (using negatives):", max_heap)  # [-5, -1, -3]

# 최대값을 추출 (삭제)
max_value = -heapq.heappop(max_heap)
print("Heap after pop:", [-x for x in max_heap])  # [3, 1]

 

 

활용 예시

• 우선순위 작업 처리: 긴급한 작업이 먼저 처리되는 환경에서는 최대 힙이나 최소 힙을 사용하여 높은 우선순위를 가진 작업을 빠르게 처리할 수 있습니다.
• 알고리즘 최적화: 다익스트라와 같은 그래프 알고리즘에서 최소 비용 경로를 빠르게 찾는 데 사용됩니다.