Heap 자료구조 [Python / 파이썬]

-목차-

1. Heap 자료구조란?

2. 힙(heap)의 삽입

3. 힙(heap)의 삭제

4. 파이썬 힙 자료구조

    4.1 heapq 모듈의 주요 메서드

    4.2 파이썬에서 최대 힙 사용하기

1. Heap 자료구조란?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

• A가 B의 부모노드(parent node) 이면, A의 키(key) 값과 B의 키값 사이에는 대소 관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 '최대 힙', 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소 관계가 정해지지 않는다.

각 노드의 자식노드의 최대 개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식 노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

---

2. 힙(heap)의 삽입

힙의 삽입 과정은 아래와 같다.

1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 새로운 노드를 부모 노드들과 교환하여 힙의 성질을 만족시킨다.

아래의 최대 힙(max heap)에 새로운 요소 삽입과정을 자세히 알아보자.

 

 

---

3. 힙(heap)의 삭제

힙에서의 삭제 과정은 아래와 같다.

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힘을 힙의 속성에 맞도록 재구성 한다.

아래의 최대 힙(max heap)에서 삭제 과정을 자세히 살펴보자.

 

 

---

4. 파이썬 힙 자료구조

힙을 구현하는 표준적인 자료구조는 배열이다.

배열로 구현된 힙에서 부모 노드와 자식 노드 간의 관계를 아래와 같이 표현된다.

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k, 2k+1) 보다 작거나 같은 최소 힙의 형태로 정렬된다. 

 

4.1 heapq 모듈의 주요 메서드

• heapq.heappush(heap, item) : item을 heap에 삽입
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop 하여 반환

아래 예시는 힙을 생성하여 원소를 삽입하고 삭제하는 예시이다. 

>>> import heapq

>>> heap = []
>>> heapq.heappush(heap, 30)
>>> heapq.heappush(heap, 10)
>>> heapq.heappush(heap, 20)

>>> print(heap)
[10, 30, 20]
>>> print(heapq.heappop(heap))
10
>>> print(heapq.heappop(heap))
20
>>> print(heapq.heappop(heap))
30

 

힙에 원소를 삽입하고 결과를 확인해 보면 최소 힙의 상태를 유지함을 확인할 수 있다. 또한 힙에서 원소를 pop할 경우 루트 노드에 해당하는 가장 작은 값이 힙에서 삭제되어 반환됨을 확인할 수 있다.

 

4.2 파이썬에서 최대 힙 사용하기

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.  이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.

아래의 예시는 리스트 heap_items에 있는 원소들을 max_heap이라는 최대 힙 자료구조로 만드는 코드이다.

>>> heap_items = [1,3,5,7,9]

>>> max_heap = []
>>> for item in heap_items:
>>>   heapq.heappush(max_heap, (-item, item))

>>> print(max_heap)
[(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]

 

---

참고 자료

https://ko.wikipedia.org/wiki/힙(자료 구조)

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://littlefoxdiary.tistory.com/3