[py] What is heap? _ 그리고 파이썬의 heapq

Programmers 문제를 풀다가 heap에 대한 정리와 heapq에 대한 복습이 필요하다는 생각 들어 정리를 하려고 한다.

 

힙(Heap)이란?

힙은 각각의 노드가 특정 속성을 가지는 완전 이진 트리다.

이 속성은 힙의 종류에 따라 다르며, 대표적으로 최대 힙(max heap)과 최소 힙(min heap)이 있다.

 

최대 힙(max heap)

최대 힙에서는 부모 노드의 key 값이 자식 노드의 key 값보다 항상 크거나 같다.

 

| | 부모 노드 P와 자식 노드 C가 있을 때 P.key >= C.key를 만족한다.

 

이러한 속성에 따라  Tree의 root에는 항상 가장 큰 값이 위치한다.

이로 인해 힙에서 가장 큰 값을 찾는 것은 root node에 접근하는 것만으로 가능하다.

 

최소 힙(min heap)

반대로 최소 힙에서는 부모 노드의 key 값이 그 자식 노드의 key 값보다 항상 작거나 같다.

 

|| 부모 노드 P와 자식 노드 C가 있을 때 P.key <= C.key를 만족한다.

 

따라서 Tree의 root에는 항상 가장 작은 값이 위치하게 된다.

최소 힙에서 가장 작은 값을 찾기 위해서는 root node에 직접 접근하면 된다.

 

Python의 heapq 모듈

Python에서 제공하는 heapq 모듈은 이러한 heap 구조를 사용해 데이터를 처리한다.

이 모듈은 heap을 배열로 표현하고 index를 통해 node 접근할 수 있다.

heapq는 최소 heap 구조를 사용하므로 heap에 추가된 가장 작은 요소가 항상 root에 위치한다.

 

예를 들어 아래와 같은 리스트가 있다고 생각해보자.

[1,3,5,7,9,2,4,6,8,0]

이 리스트를 힙으로 만들면 가장 작은 값인 0이 root node에 위치한다.

 

heapq의 주요 함수

 

1. heapify(iterble)

일반적인 리스트를 힙의 형태로 바꿔준다.

변환된 힙은 위에서 정리한 힙의 성질을 만족한다.

import heapq
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(nums)
print(nums)  # 출력: [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

2. heappush(heap, el)

heap에 새 요소를 push해준다.

새로운 요소를 힙에 추가한 후 힙의 성질이 유지되도록 힙을 재구성한다.

heapq.heappush(nums, -5)
print(nums)  # 출력: [-5, 1, 1, 3, 3, 2, 4, 6, 5, 5, 5, 9]

 

3. heappop(heap)

힙에서 가장 작은 요소를 pop한다.즉 가장 작은 요소를 제거하고 반환한 후 힙의 성질이 유지되도록 힙을 재구성해준다.

print(heapq.heappop(nums))  # 출력: -5
print(nums)  # 출력: [1, 1, 2, 3, 3, 4, 6, 5, 5, 5, 9]

 

4. heappushpop(heap, el)

힙에 새로운 요소를 push하고 가장 작은 요소를 pop한다.heappush() 호출 후 heappop()을 호출하는 것보다 효율적으로 작동한다.

import heapq

heap = [3, 5, 7, 9, 11]

# heappushpop()을 사용하여 새로운 요소 6을 힙에 추가하고, 가장 작은 요소 3을 제거합니다.
new_element = 6
min_element = heapq.heappushpop(heap, new_element)

print("Heap:", heap)         # 출력: [5, 6, 7, 9, 11]
print("Min Element:", min_element)   # 출력: 3

 

5. heapreplace(heap, el)

heappushpop()과 비슷하게 작동하지만 먼저 가장 작은 요소를 pop하고 그 다음 새 요소를 push한다.

import heapq

heap = [3, 5, 7, 9, 11]

# heapreplace()를 사용하여 가장 작은 요소를 제거하고, 새로운 요소 4를 힙에 추가합니다.
new_element = 4
min_element = heapq.heapreplace(heap, new_element)

print("Heap:", heap)         # 출력: [4, 5, 7, 9, 11]
print("Min Element:", min_element)   # 출력: 3

 

6. nlargest(n, iterable, key=None) / nsmallest(n, iterable, key=None)

주어진 iterable에서 가장 큰 n개의 요소 또는 가장 작은 n개의 요소를 반환한다.

# nlargest

import heapq

numbers = [15, 3, 9, 12, 5, 1, 8, 6]

# nlargest()를 사용하여 numbers에서 가장 큰 3개의 요소를 반환합니다.
largest_elements = heapq.nlargest(3, numbers)

print("Largest Elements:", largest_elements)   # 출력: [15, 12, 9]

 

# nsmallest

import heapq

numbers = [15, 3, 9, 12, 5, 1, 8, 6]

# nsmallest()를 사용하여 numbers에서 가장 작은 4개의 요소를 반환합니다.
smallest_elements = heapq.nsmallest(4, numbers)

print("Smallest Elements:", smallest_elements)   # 출력: [1, 3, 5, 6]