[Python] 프로그래머스 Heap 강의자료

※본 포스팅은 프로그래머스 pccp 교육자료를 참고하였습니다.

 

힙(Heap)

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 우선순위 큐(Priority Queue)를 구현하는 데 자주 사용됩니다.
최댓값 또는 최솟값을 빠르게 찾을 수 있는 성질을 가지며, 힙 정렬에도 활용됩니다.

---

1. 힙의 종류

1. 최소 힙(Min-Heap):
   • 부모 노드가 자식 노드보다 항상 작거나 같은 값.
   • 루트 노드에는 가장 작은 값이 저장됨.
2. 최대 힙(Max-Heap):
   • 부모 노드가 자식 노드보다 항상 크거나 같은 값.
   • 루트 노드에는 가장 큰 값이 저장됨.

---

2. 힙의 특징

1. 완전 이진 트리:
   • 마지막 레벨을 제외하고 모든 레벨이 꽉 차 있으며, 마지막 레벨도 왼쪽부터 채워짐.
2. 힙 속성:
   • 최소 힙: 부모 노드 ≤ 자식 노드.
   • 최대 힙: 부모 노드 ≥ 자식 노드.
3. 효율적인 삽입 및 삭제:
   • 힙에서 삽입과 삭제 연산은 O(log⁡ n)의 시간 복잡도를 가집니다.
4. 배열을 이용한 구현:
   • 힙은 배열로 구현되며, 노드의 인덱스 관계를 이용해 부모와 자식 노드 간의 관계를 관리합니다.
     • 부모: (i - 1) // 2
     • 왼쪽 자식: 2i + 1
     • 오른쪽 자식: 2i+22i + 2

---

3. 힙의 구현

(1) 파이썬에서 제공하는 힙 라이브러리

파이썬의 heapq 모듈은 최소 힙을 기본으로 제공합니다.

heapq 주요 함수

함수설명

heapify(iterable)	리스트를 힙 구조로 변환
heappush(heap, item)	힙에 요소 삽입
heappop(heap)	힙에서 가장 작은 요소 제거 및 반환
heappushpop(heap, item)	새 요소를 삽입 후 가장 작은 요소 제거 및 반환
heapreplace(heap, item)	가장 작은 요소를 제거하고 새 요소 삽입
nlargest(n, iterable)	힙에서 가장 큰 n개의 요소 반환
nsmallest(n, iterable)	힙에서 가장 작은 n개의 요소 반환

---

(2) 최소 힙 구현

import heapq

# 힙 생성
heap = []

# 요소 삽입
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 30)

print("힙 상태:", heap)  # [5, 10, 30] (항상 정렬된 형태 유지)

# 가장 작은 값 제거
min_value = heapq.heappop(heap)
print("제거된 값:", min_value)  # 5
print("힙 상태:", heap)  # [10, 30]

---

(3) 최대 힙 구현

파이썬의 heapq는 기본적으로 최소 힙을 제공하므로, 최대 힙을 구현하려면 음수 값으로 변환하여 사용합니다.

import heapq

# 힙 생성
heap = []

# 요소 삽입 (음수로 변환)
heapq.heappush(heap, -10)
heapq.heappush(heap, -5)
heapq.heappush(heap, -30)

# 최대 값 제거
max_value = -heapq.heappop(heap)
print("제거된 최대값:", max_value)  # 30

---

(4) 리스트를 힙으로 변환

heapify를 사용하면 리스트를 힙 구조로 변환할 수 있습니다.

import heapq

nums = [10, 5, 20, 1, 7]
heapq.heapify(nums)  # 리스트를 힙 구조로 변환
print("힙 상태:", nums)  # [1, 5, 20, 10, 7]

# 가장 작은 값 제거
min_value = heapq.heappop(nums)
print("제거된 값:", min_value)  # 1

---

4. 힙의 활용

(1) 우선순위 큐

힙은 우선순위 큐를 구현하는 데 사용됩니다.

import heapq

# 우선순위 큐 생성 (우선순위, 값)
priority_queue = []
heapq.heappush(priority_queue, (2, "Task A"))
heapq.heappush(priority_queue, (1, "Task B"))
heapq.heappush(priority_queue, (3, "Task C"))

# 우선순위가 가장 높은 작업 처리
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"처리할 작업: {task} (우선순위: {priority})")
# 출력:
# 처리할 작업: Task B (우선순위: 1)
# 처리할 작업: Task A (우선순위: 2)
# 처리할 작업: Task C (우선순위: 3)

---

(2) K번째 최소 또는 최대 값 찾기

import heapq

nums = [7, 10, 4, 3, 20, 15]

# 3번째 최소 값
kth_min = heapq.nsmallest(3, nums)[-1]
print("3번째 최소 값:", kth_min)  # 7

# 2번째 최대 값
kth_max = heapq.nlargest(2, nums)[-1]
print("2번째 최대 값:", kth_max)  # 15

---

(3) 힙 정렬

힙을 사용해 정렬을 구현할 수 있습니다.

import heapq

def heap_sort(nums):
    heapq.heapify(nums)  # 리스트를 힙으로 변환
    sorted_nums = [heapq.heappop(nums) for _ in range(len(nums))]
    return sorted_nums

nums = [10, 5, 20, 1, 7]
print("정렬 결과:", heap_sort(nums))  # [1, 5, 7, 10, 20]

---

5. 시간복잡도

연산시간복잡도

삽입 (heappush)	O(log n)
삭제 (heappop)	O(log n)
최소값 접근 (heap[0])	O(1)
리스트 힙화 (heapify)	O(n)

---

6. 힙의 장단점

장점

1. 효율적:
   • 삽입과 삭제가 O(log n)로 빠르게 수행.
2. 간단한 구현:
   • heapq 모듈로 쉽게 구현 가능.
3. 다양한 활용:
   • 우선순위 큐, 정렬, 최솟값/최댓값 계산 등.

단점

1. 모든 값을 정렬하지 않음:
   • 힙은 전체를 정렬하지 않고 최솟값/최댓값만 빠르게 접근.
2. 특정 값 검색이 비효율적:
   • 힙에서 특정 값을 찾는 데 O(n)소요.

---

7. 정리

• 힙의 주요 용도:
  • 우선순위 큐, K번째 최소/최대 값 찾기, 힙 정렬.
• 파이썬의 heapq 모듈:
  • 최소 힙을 기본으로 제공하며, 최대 힙은 음수를 활용.
• 효율성:
  • 삽입과 삭제가 O(log⁡ n)로 빠르고, O(1)로 최솟값에 접근 가능.