[TIL]0726_Heap(heapq모듈)

Heap

• 부모 노드 ≦ 자식 노드 값을 갖는 이진 트리
• 최대, 최소값 가져올 때 많이 사용
• heapq 모듈은 이진트리(binary tree) 기반 최소 힙(min heap) 자료구조 제공

힙과 관련된 함수(import heapq)

• 생성: heap = [ ]
• 추가: heapq.heappush(heap, item) = item 값을 heap으로 push
• 제거: heapq.heappop(heap, item) = 가장 작은 원소 값 제거 후 그 값 리턴
• 리스트 ▶️ 힙: heapq.heapify(heap)
• 최소 값(루트 노드): heap[0]

import heapq                            # 모듈 import

heap = []                               # heap 생성

# heap에 원소 추가
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)
print(heap)
>>> [1, 2, 4, 3]

# heap에서 원소 삭제		
print(heapq.heappop(heap))		# 가장 작은 원소 삭제 후 그 값 리턴
print(heap)
>>> 1
>>> [2, 4, 3]

# 최소 값
print(heap[0]
>>> 2

# 리스트 ▶️ 힙
heap = [2, 5, 1, 4, 9]
heapq.heapify(heap)
print(heap)
>>> [1, 4, 2, 5, 9]

힙 정렬

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# while문 이용
def heap_sort(nums):
    h = []
    for num in nums:
        heapq.heappush(h1, num)

    sorted_nums = []
    while h:
        sorted_nums.append(heapq.heappop(h))
    return sorted_nums

print(heap_sort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

최대 힙(Max heap)

• heapq 모듈은 최소 힙만 동작 따라서 최대 힙으로 하기 위해서는
• 힙에 튜플(tuple)을 원소로 추가, 삭제하면 튜플 내에서 맨 앞에 있는 값 기준으로 최소 힙이 구성되는 원리 이용
• 최대 힙을 만들기 위해서는
  1. 각 값에 대한 우선 순위 구하기(우선 순위 값)
  2. 구조의 튜플(tuple)을 힙에 추가, 삭제하면 된다.
  3. 힙에서 갑을 읽어 올 때 각 튜플에서 인덱스 1에 있는 값을 취하면 된다.
  

import heapq

nums = [5, 1, 7, 3, 9]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))   # (우선 순위, 값)

while heap:
    print(heapq.heappop(heap)[1])
   
>>> 9
>>> 7
>>> 5
>>> 3
>>> 1

---

🍎느낀점

• 자료구조를 계속 C로 공부하다가 파이썬으로 다시 공부하려고 하는데 역시 훨씬 편하다👍🏻
• 파이썬 힙은 미니힙이 디폴트인가?
• 아직도 헷갈리는 함수들이 많아 좀 더 공부해봐야겠다

참고: https://jungeun960.tistory.com/146?category=468716
https://docs.python.org/ko/3/library/heapq.html#