[자료구조/파이썬(Python3)] 힙 (Heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성을 만족합니다.

 

- A가 B의 부모노드이면, A의 key 값과 B의 key 값 사이에는 대소관계가 성립한다.

 

그래서 대소관계에 따라 힙에는 두 가지 종류가 있습니다.

- 최소 힙(min heap) : 부모노드의 키 값이 자식노드의 키값보다 항상 작은 힙

- 최대 힙(max heap) : 부모노드의 키 값이 자식노드의 키값보다 항상 큰 힙

 

코딩테스트에서 최솟값이나 최댓값을 반복해서 호출해야하는 경우, heap을 사용해서 효율성을 증가시킬 수 있습니다.

출처: https://medium.com/@dwang0816/binary-heap-4bac5f79c60b

 

 

 

파이썬에는 heapq 모듈로 힙 알고리즘을 제공합니다.

import heapq

 

heapq에서는 기본적으로 최소힙을 지원합니다.

최대힙을 구현하려면 heapq의 최소힙을 응용하면 됩니다.

 

 

힙 시작하기

1. 힙 생성하기

- heappush(heap, item) : 빈 리스트(heap)를 만들어서 원소(item)를 추가하거나
- heapify(list) : 리스트를 힙으로 바꾸거나

 

빈 리스트에 원소를 추가해서 힙을 생성하는 방법입니다.

heap = []

heapq.heappush(heap, 5)
heapq.heappush(heap, 8)
heapq.heappush(heap, 2)

print (heap)  # [2, 5, 8]

 

리스트를 힙으로 바꾸는 방법입니다.

lst = [8,3,5]
heapq.heapify(lst)

print (lst)  # [3, 5, 8]

 

 

2. 힙에서 원소 삭제하기

- heappop(heap) : 힙(heap)에서 가장 작은 원소를 제거함

힙 요소를 한 개 씩 삭제할 수 있습니다.

요소를 삭제해도 힙구조는 계속 유지됩니다.

 

import heapq
temp_heap = [1,6,38,59]

print(heapq.heappop(temp_heap)) # 1
print(temp_heap)  # [6, 38, 59]

첫 번째 print문에서는 제거되는 원소를 출력합니다.

두 번째 print문에서는 최소값이 제거된 힙을 출력합니다.

 

 

3. 최대 힙

heapq 모듈은 최소힙 기능만 가능하기 때문에 최대힙은 응용해서 구현해야합니다.

다양한 방법 중에서도 (우선순위, 값) 구조를 활용한 방법이 유용하게 쓰입니다.

nums = [8, 3, 4, 9, 5, 7]
tuple_heap = []   # 튜플값을 담을 임시 힙
max_heap = []     # 최대값 순으로 원소를 담을 빈 리스트

for num in nums:
  heapq.heappush(tuple_heap, (-num, num))  # (우선 순위, 값)
  
print(tuple_heap)
# [(-9, 9), (-8, 8), (-7, 7), (-3, 3), (-5, 5), (-4, 4)]

for i in range(len(tuple_heap)):
    a=heapq.heappop(tuple_heap)[1]
    max_heap.append(a)
    
print(tuple_heap)
# []

print(max_heap)
# [9, 8, 7, 5, 4, 3]

-를 붙여서 nums 리스트의 원소를 음수값으로 만들어준 뒤, 원래의 원소와 짝을 지어 튜플로 저장합니다.

그래서 첫 번째 print 문에서 튜플값을 담을 임시 힙이 출력된 것을 확인할 수 있습니다.

 

두 번째 for 문에서 아래의 코드가 최대힙을 만드는 데 중요한 역할을 합니다.

a=heapq.heappop(tuple_heap)[1]

a=heapq.heappop(tuple_heap) 로 두면 a는 (-9, 9) 입니다.

튜플의 첫 번째 인덱스값인 음수인 숫자들로 최소힙을 적용한 것입니다.

 

그런데,

a=heapq.heappop(tuple_heap)[0] 으로 하면 a는 -9 로 할당되고,

a=heapq.heappop(tuple_heap)[1] 으로 하면 a는 9로 할당됩니다.

 

이 점을 이용해서 a 값을 max_heap에 넣어주면 최대힙이 구현됩니다.

 

 

힙을 사용한 코딩테스트 문제 확인하러 가기 ↓↓↓↓↓

https://data-analysis-expertise.tistory.com/102

[프로그래머스/2단계/파이썬(Python3)] 더 맵게

 

https://data-analysis-expertise.tistory.com/103

[백준/1927/파이썬(Python3)] 최소힙