Heap 구조 설명 및 파이썬 예제

힙(Heap)은 이진 트리 기반의 자료구조로, 힙 속성(Heap Property)을 만족합니다:
- 최소 힙(Min-Heap): 모든 부모 노드는 자식 노드보다 작거나 같습니다.
- 최대 힙(Max-Heap): 모든 부모 노드는 자식 노드보다 크거나 같습니다.

** 힙은 정렬된 구조는 아니지만, 가장 작은 값(또는 가장 큰 값)이 항상 루트(최상단)에 위치한다는 것을 보장합니다.

 

1. 최소 힙 예제

다음 입력이 주어지면: [5, 3, 8, 1, 2]

최소힘은 다음과 같은 이진 트리로 입력 갑을 변환함:

그리고 새롭게 저장된 배열은 다음과 같음: [1, 2, 8, 5, 3]
각 노드의 인덱스 i에 대해서:
왼쪽 자식 노드 = 인덱스 2i + 1
오른쪽 자식 노드 = 인덱스 2i + 2

 

2. 실제 힙 구조가 사용되는 경우들

1) 우선순위 큐
2) 스케줄링 시스템
3) Dijkstra 최단 경로
4) Top-K 찾기
5) 힘 정렬

 

3. 파이썬: heapq 모듈

파이썬의 내장 함수 'heapq' 모듈은 최소 힙을 기본적으로 지원합니다. 따라서 만일 최대 힙을 구현하려면 힙을 구성할 항목들을 모두 음수로 전환하여 처리하면 됩니다.

 

4. 파이썬 예제: 최소 힙

[min_heap.py]

import heapq

# 리스트로부터 힙을 구성
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print("Min-Heap:", nums)  # 최소 항목이 인덱스 0에 있음

[output]
Min-Heap: [1, 2, 8, 5, 3]

참고: 힙은 리스트 형태로 저장된 이진 힙이며, 완전히 정렬된 것은 아니고 힙 속성을 유지하도록 구조화되어 있습니다.

 

5. Heap 함수들

1) heapq.heappush(heap, item)

[힙에 원소를 추가]

heapq.heappush(nums, 0)
print(nums)  # [0, 2, 1, 5, 3, 8]

2) heapq.heappop(heap)

[최소 원소를 출력하고 힙에서 삭제한다]

smallest = heapq.heappop(nums)
print("Smallest:", smallest)  # 0
print("Heap after pop:", nums)

3) heapq.heappushpop(heap, item)

[새로운 원소를 힙에 추가하고 최소 원소를 출력 후 힙에서 삭제한다]

result = heapq.heappushpop(nums, 4)
print("Result:", result)  # 최소원소 출력

4) heapq.nsmallest(n, iterable)

[힙 구조 변경없이 최소 원소를 반환]

heapq.nsmallest(3, nums)  # [1, 2, 3]

 

6. 문제: Top-K 최대 (혹은 최소) 원소들 찾기

숫자들이 주어졌을 때 top-k의 최대 (혹은 최소) 원소들을 찾아 줌.

Using heapq.nlargest() and heapq.nsmallest()

import heapq

nums = [4, 1, 7, 3, 8, 5, 10, 2]

# Top 3 최대 값들
top_k_largest = heapq.nlargest(3, nums)

# Top 3 최소 값들
top_k_smallest = heapq.nsmallest(3, nums)

print("Top 3 Largest:", top_k_largest)
print("Top 3 Smallest:", top_k_smallest)

[Output]
Top 3 Largest: [10, 8, 7]
Top 3 Smallest: [1, 2, 3]

이 함수들은 내부적으로 매우 효율적으로 동작합니다:

- nlargest(k, iterable)는 k 크기의 최소 힙을 사용합니다.
- nsmallest(k, iterable)는 값들을 부호 반전하여 크기 k의 최대 힙을 사용합니다

Top-K 힙 직접 개발

최대 3개의 가장 큰 값을 직접 찾고 싶다고 가정해봅시다. 이때 크기 k의 최소 힙을 사용합니다.

import heapq

def top_k_largest(nums, k):
	min_heap = nums[:k]
    heapq.heapify(min_heap)  # 첫번째 k원소들을 min-heap으로 변환

    for num in nums[k:]:
        if num > min_heap[0]:  # 힙의 최소값 보다 클 경우만 삽입
            heapq.heappushpop(min_heap, num)

    return sorted(min_heap, reverse=True)

nums = [4, 1, 7, 3, 8, 5, 10, 2]
top3 = top_k_largest(nums, 3)
print("Top 3 largest:", top3)

[Output]
Top 3 largest: [10, 8, 7]