[파이썬] 파이썬 heapq(힙큐) / 프로그래머스 더 맵게

힙큐 알고리즘

 

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.1 문서

 

소스 코드 : Lib/heapq.py

 

heapq(힙큐)는 파이썬의 내장 모듈로, 이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조이다. 

 

tree(트리)

 

그래프와 함께 비 선형 구조로 루트 노드로 부터 가지를 뻗어나가는 형태를 취하고 있다. 트리는 이진트리(binary tree)는 자식 노드로 최대 2개의 노드(왼쪽 자식 노드, 오른쪽 자식 노드)를 가질 수 있는 구조다.

 

heap

 

힙은 완전 이진 트리를 기본으로 하는 자료구조로, 파이썬의 경우 리스트로 구현된다고 한다. 힙의 종류로는 max heap(최대 힙)과 min heap(최소 힙)이 있는데 둘의 차이는 값의 크기 차이다.

 

최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 상태의 힙이고 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 상태의 힙이다.

 

앞서 말한대로 파이썬에서 heapq(힙큐)는 최소 힙(min heap) 자료구조이다. 부모 노드의 키 값이 항상 자식 노드의 키 값보다 크다. 

 

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리입니다. 이 구현에서는 모든 
k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다, 요소는 0부터 셉니다.
비교를 위해, 존재하지 않는 요소는 무한으로 간주합니다. 힙의 흥미로운 특성은 가장 작은 요소가 항상 루트인 heap[0]이라는 것입니다.

 

파이썬 heapq(힙큐)

 

사용법

 

import heapq

 

힙큐는 파이썬 내장 모듈이기 때문에 import 하여 사용할 수 있다.

 

힙을 만들려면, []로 초기화된 리스트를 사용하거나,
함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환할 수 있습니다.

 

heapq.heappush(heap, item)

 

힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

 

import heapq

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 6)

print(heap)
#[1, 3, 5, 4, 6]

 

가장 작은 값인 1이 index 0의 위치하고, 나머지 index에 위치한 값은 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]을 만족한다. index 1의 값 3은 index 3(2*1 + 1 = 3)의 4와 index 4(2*2 + 1 = 4)의 6보다 작은 값을 만족한다. heappush() 함수는 O(logN)의 시간 복잡도를 가진다.

 

heapq.heappop(heap)

 

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝 하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스 하려면, heap[0]을 사용하십시오.

 

import heapq

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 6)

heapq.heappop(heap)
print(heap)         # [3, 4, 5, 6]
heapq.heappop(heap)
print(heap)         # [4, 6, 5]
print(heap[0])      # 4

 

heappop() 함수를 통해 원소를 삭제할 수 있다. 인자로 리스트를 넘기면 해당 리스트에서 가장 작은 원소를 삭제하고 그 값을 리턴해 준다. 첫 번째 heappop(heap)을 한 경우 가장 작은 원소인 1이 삭제되고 3이 index 0의 위치로 옮겨졌다. 두 번째도 같은 방식이고, 정렬의 기준은 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]을 만족한다.

 

가장 작은 원소를 삭제하지 않고 얻는 방법은 리스트의 첫 번째 원소에 접근하면 된다(heap[0]).

 

여기까지 []로 초기화된 리스트를 사용하여 힙큐를 사용한 것이고, 기존의 리스트를 힙으로 변환하는 방법은 다음과 같다.

 

heapq.heapify(x)

 

리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

 

import heapq

tmp = [1, 2, 3, 9, 10, 12]
heapq.heapify(tmp)
print(type(tmp))    # <class 'list'>

tmp.append(1)
print(tmp)          # [1, 2, 3, 9, 10, 12, 1]

heapq.heappush(tmp, 1)
print(tmp)          # [1, 1, 3, 2, 10, 12, 1, 9]

 

기존에 선언되어 있던 리스트 tmp를 힙으로 변환하려면 heapq.heapify(tmp)를 실행하면 된다. 변환한 후에도 tmp는 리스트의 성질을 그대로 가지고 있다. 따라서 append()와 같은 연산도 가능하다. 힙큐로 변환했기 때문에 heappush() 연산도 가능하고, 연산 후에는 힙큐의 성질에 따라 재 정렬된다.

 

---

예제

 

코딩테스트 연습 - 더 맵게

 

예제 풀이

 

Feat : 더 맵게 · mieumje/Python_Coding_Test@aa35125