10. 힙(Heap)
10-5. heapq 라이브러리 사용
heapq 라이브러리는 파이썬의 표준 라이브러리인 heapq 모듈을 의미.
이 모듈은 힙(heap) 자료구조를 구현하는 함수와 알고리즘을 제공.
import heapq as hq
import random as r
# random.randint()
list_data = [r.randint(1,30) for _ in range(6)] # 1부터 30까지 6개의 숫자를 무작위로 뽑음
print(list_data)
print()
# 최소 힙 : 기록순 정렬
print('힙 만들기')
hq.heapify(list_data) # heapify(): 리스트를 힙으로 변환하는 역할
print(list_data)
# print(list_data.pop(0)) # 맨 앞의 숫자를 제거하여 반환하는 경우 1
# print(list_data)' # 이후 출력한 힙
hq.heappop(list_data) # 맨 앞의 숫자를 제거하여 반환하는 경우 2
print(list_data)
print()
print('최대힙 만들기')
hq._heapify_max(list_data) # _heapify_max(): 최대 힙(max heap)으로 리스트를 변환하는 내부적인 함수
print(list_data)
hq.heappop(list_data)
print(list_data)
==========================================================
import heapq
import random
class MaxHeap:
def __init__(self):
self.data = [ ]
def top(self): # 힙에서 가장 큰 값을 반환하는 메서드
return -self.data[0]
# heapq 모듈은 최소 힙을 기본으로 지원하므로,
최대 힙을 구현하기 위해 -self.data[0]와 같이 음수로 변환하여 반환함.
def push(self, val): # 힙에 값을 추가하는 메서드.
heapq.heappush(self.data, -val)
# heapq 모듈이 최소 힙을 지원하기 때문에 최대 힙을 구현하기 위해 음수 값을 활용
def pop(self): # 힙에서 가장 큰 값을 제거하고 반환하는 메서드
return -heapq.heappop(self.data)
# 마찬가지로, 최소 힙을 기반으로 동작하는 heapq 모듈을 활용하므로
-heapq.heappop(self.data)와 같이 음수 값을 반환
mxh = MaxHeap()
for _ in range(5):
item = random.randint(1,20)
print(item, end = ' ')
mxh.push(item)
print()
print(mxh.data)
print(mxh.top())
