[python] heapq: 힙이란? 파이썬에서 힙을 사용하고 싶을 때

 

 

 

먼저, 큐에 대해 다시 생각해보자

일반적인 큐는 FIFO 구조로 먼저 들어온 요소가 먼저 나가는 자료구조이다

 

우선순위 큐도 있다

우선순위 큐는 데이터들이 우선순위를 가지고 우선순위가 높은 요소가 먼저 나가는 자료구조이다

 

바로 이 우선순위 큐를 위한 자료구조가 힙이다

배열, 연결리스트, 힙 으로 구현이 가능한데 힙으로 구현하는 것이 O(log n)으로 구현하는 것이 가장 효율적이다(나머진 O(n))

 

 

 

 

 

그럼 힙(heap)이란?

 

• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 완전 이진 트리이며, 시간복잡도는 O(log n)에 추가와 삭제가 가능하다
• 최대힙, 최소힙 2가지 종류가 있다
  • 최대힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
    
  • 최소힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

 

 

 

python의 heapq

 

python의 heapq는 최소힙 구현을 제공하며 요소를 추가하고 제거하는 기능을 제거한다

최대힙을 제공하는 것이 아니라 최소힙만 제공한다

 

• heappush(heap, item) : item을 heap에 추가
• heappop(heap) : heap에서 가장 작은 원소 제거 & 리턴
• heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 ( O(N) )

 

다음과 같이 활용할 수 있다

 

from heapq import *

a = [5, 3, 4, 1, 2]     
heapify(a)              # [1,2,3,4,5]
print(a[0])             # 1(최솟값)

print(heappop(a))       # 힙에 최솟값 제거
print(a[0])             # 2

heappush(a, 7)          # 힙에 7을 추가
print(a[0])             # 2

heappush(a, 0)
print(a[0])             # 0

 

 

 

 

 

최대힙 만들기

 

 

최소힙만 구할 수 있지만 -를 이용하여 최대힙도 구할 수 있다

튜플 등 다양한 방법으로 구하긴 하지만 간단하게 예시를 들자면

 

1. 10, 1, 5를 넣는다 가정했을 경우
2. -를 넣어서 최소힙을 구함
3. 사용할 때 다시 -

 

from heapq import *

max_heap = []

#10, 1, 5
heappush(max_heap, -10)
heappush(max_heap, -1)
heappush(max_heap, -5)

max_element = max_heap[0]
print(-max_element)