힙(Heap)구조에 대해서 알아보자(python 내장 모듈 heapq)

Heap의 특징

a = [3, 8, 5, 2]
heapq.heapify(a)
print(a)

- 원소들이 항상 정렬된 상태로 추가되고 삭제됨(binary tree 기반)

- 최소 힙(min heap)이라고 칭함

- 최소 힙은 root 즉 idx 0에 위치한 값이 가장 작고 자식들은 root보다 같거나 작음

- 즉, 최소 힙의 root는 최소값이니 이 성질을 잘 기억하자

- 따라서, 노드들도 자식들보다 같거나 작음

1. 내장모듈 heapq 불러오기

import heapq​

 

2. heap 생성하기

- heapq 모듈을 사용하면 python의 일반 리스트를 heap 구조로 사용할 수 있게해줌

heap = []

 

3. 힙에 element 넣어주기 : heappush( )

heapq.heappush(heap, 6)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)
heapq.heappush(heap, 1)
print(heap)

[1, 2, 3, 6]

4. 힙에 element 넣어주기2 : heappush( )

heapq.heappush(heap, 5)
heapq.heappush(heap, 4)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

[1, 3, 7, 5, 4, 8]

5. 힙에 element 빼내기 : heappop( )

- heappop( )을 하면 그냥 pop( )과 달리 가장 작은 값이 pop됨

print(heapq.heappop(heap))
print(heap)

1
[2, 3, 6]

 

6. 이미 element가 채워져있는 리스트를 heap구조로 만들기 : heapify( )

- list를 heap화 해준다고 생각하자

heap = [8, 3, 5, 2]
heapq.heapify(heap)
print(heap)

[2, 3, 5, 8]

 

참고 url

https://www.daleseo.com/python-heapq/