[파이썬] Heap 자료구조 (import heapq)

자 이번 코테 스터디는 힙 문제들이다

그래서 들어가기에 앞서 힙 자료구조 공부를 좀 하려고 한다

물론 c++ 아직 포기 못해서 c++도 정리할거임~

---

파이썬은 heapq 모듈을 제공한다

heapq 모듈은 최소 힙을 지원하는 모듈로, 직접 최소 힙을 구현하지 않아도 된다!

 

 

데이터 추가

데이터 추가는 heapq.heappush(힙 이름, 데이터) 이런식으로 하면 된다

import heapq

heapq.heappush(heap_name, 13) #heap_name 자리에 heap 이름을 넣는다
print(heap_name)
# [13]

heapq.heappush(heap_name, 1)
print(heap_name)
# [1, 13]

heapq.heappush(heap_name, 6)
print(heap_name)
# [1, 6, 13]

heapq.heappush(heap_name, 8)
print(heap_name)
# [1, 6, 8, 13]

heapq.heappush(heap_name, 12)
print(heap_name)
# [1, 6, 8, 12, 13]

 

 

 

데이터 삭제

최소, 최대 힙에서 데이터 삭제는 루트 노드를 삭제하는 것이 일반적이기 때문에 heapq에서는 루트 노드만 삭제가 가능하다

데이터 삭제는 heapq.heappop(힙 이름) 이렇게 하면 루트 노드가 삭제된다

# heap_name = [1, 6, 8, 10, 14, 12]

heapq.heappop(heap_name)
print(heap_name)
# [6, 8, 10, 14, 12]

 

 

 

 

리스트 변환

기존 리스트를 heapq.heapify(리스트 이름) 함수를 통해 최소 힙으로 변환할 수 있다

_list = [14, 10, 6, 8, 12, 4]
heapq.heapify(_list)
print(_list)
#[4, 8, 6, 10, 12, 14]

 

 

 

최대 힙 표현하기

heapq 모듈은 최소 힙만 지원하기 때문에 최대 힙을 만드려면 입력 값들에 음수를 씌우면 된다!

reverse_sign = lambda x : x*-1
max_heap = list(map(reverse_dign, _list))
heapq.heapify(max_heap)
max_heap = list(map(revserse_sign, max_heap))

#[14, 12, 6, 8, 10, 4]

 

 

 

힙 정렬

sorted() 함수를 사용해도 되지만, 힙 정렬을 구현해야만 한다면 아래와 같이 구현할 수 있다

import heapq

_list = [14, 10, 6, 8, 12, 4]
heapq.heapify(_list)

method1 = []

while _list:
	method1.append(heapq.append(_list))
  
print(method)
#[4, 6, 8, 10, 12, 14]

 

 

 

---

출처)

https://brownbears.tistory.com/550

[Python] Heap과 heapq 모듈