[Python] 힙 (Heap)

heap

: 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조

• 각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리

• 키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음

• 자식노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개 (완전이진트리를 사용한다고 가정하자.)

• i번째 노드의 자식노드가 2개인데 왼쪽 자식노드는 2i, 오른쪽 자식노드는 2i+1이고, 부모노드는 i/2가 된다

• 시간복잡도
  : O(log n)

import heapq

heapq 모듈을 사용해서 최소 힙과 최대 힙을 구현할 수 있다.

내부 메소드

노드 추가 heappush(heap, item)

힙의 불변성을 유지하면서, item값을 heap으로 push해주는 메소드이다.

노드 삭제 heappop(heap)

힙의 불변성을 유지하면서, heap에서 가장 작은 항목을 pop하고 반환해주는 메소드이다.
힙이 비어있을 때 heappop메소드를 사용하면 IndexError가 발생하니 주의해야 한다.

최소 힙

• heap의 역할을 할 빈 리스트 선언
• heappush 메소드의 매개변수로 해당 리스트와 추가할 값을 넣어줌.

import heapq

heap = []

# 아래 for문을 실행하고 나면 heap은 [1,2,3,5,4]로 힙 정렬이 되게 된다.
for i in range(1,6):
	heapq.heappush(heap, i)

# 작은 숫자 순서대로 1,2,3,4,5가 출력된다.
for i in range(5):
	print(heapq.heappop(heap))

최대 힙

• heapq에서는 최대 힙은 제공하지 않으므로, 부호를 변경하여 사용한다.
• 부호를 바꿔서 최소 힙에 넣어준 후, 최솟값부터 pop해줄 때 부호를 바꿔주면 된다.
• heap의 역할을 할 빈 리스트 선언
• heappush 메소드의 매개변수로 해당 리스트와 추가할 값을 넣어줌.

import heapq

heap = []
values = [1,5,3,2,4]

# 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다.
for value in values:
	heapq.heappush(heap, -value)

# 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))