힙이란?

힙이란, 트리 구조 중에서 완전이진트리를 기반으로 하는 자료구조이다. 힙은 최댓값과 최솟값을 구하는데에 아주 탁월하다. 그 이유는 힙을 이해하고 나면 확실히 알게 될 것이다.

힙이 되기위한 만족 조건으로는 다음과 같다.

• 자식노드보다 부모노드의 값이 더 커야 한다.
• 왼쪽 자식노드보다 오른쪽 자식노드의 값이 더 커야 한다.

이미지출처

힙에는 위와 같이 두가지의 종류가 있는데, 루트노드가 가장 작은 최소 힙, 루트노드가 가장 큰 최대 힙이 있다.

파이썬에서는 이를 사용하기 편하도록 라이브러리로 제공한다.

라이브러리 불러오기

import heapq

heapq 라이브러리는 리스트를 최소힙으로 사용 가능하도록 한다. 리스트이기 때문에 인덱스값 접근으로도 활용이 가능하고, 힙이기 때문에 트리구조 탐색 방식도 사용이 가능해진다.

힙의 인덱스

힙의 인덱스는 각 깊이에 따라 인덱스 값이 주어진다.

이미지출처
n개의 원소를 가지는 리스트를 힙으로 변환하면,

• 왼쪽 자식노드의 인덱스 : 2n
• 오른쪽 자식노드의 인덱스 : 2n + 1

기존 리스트를 힙으로 사용하기

heapify() 함수를 사용한다.

list1 = [1, 2, 3, 4]
heapq.heapify(list1)

힙에 값 추가하기

heap 이라고 선언해놓은 heapq에 3 이라는 값을 추가하고 싶을 경우, 다음과 같다.

heapq.heappush(heap, 3)

heapq 내의 적절한 위치를 자동으로 찾아 추가한다.

힙에서 값 삭제하기

heapq.heappop(heap)

힙에서 가장 작은 값을 삭제하여 반환한다.
가장 작은 값이 삭제된 후에는 남은 힙 내부의 가장 작은 값이 자리를 대체한다.

최대힙은?

위에서 힙은 최소힙과 최대힙으로 사용이 가능하다고 했는데, heapq 라이브러리는 최소힙으로 사용이 가능하다고 했다. 그렇다면 heapq를 최대힙으로 어떻게 사용할 수 있을까?

바로 우선순위를 부여하는 것이다 ❗️❗️

힙에 사용하는 값을 (우선순위, 값)의 형태인 튜플로 사용하면 최대힙으로 사용이 가능하다.

list2 = [(1, 10), (2, 9), (3, 8), (4, 7)]
heapq.heapify(list2)

이렇게 되면 우선순위에 의해 루트노드의 값이 가장 큰 최대 힙으로 변경이 가능하다 😆