[파이썬 자료구조] 힙 (heap) / 힙큐 (heapq)

힙은 특정한 규칙을 가지는 트리이다.

 

최소값과 최대값을 찾는 연산을 빠르게 하기 위해 만들어진 완전이진트리를 토대로한다.

 

# 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

# 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙

 

< 이미지 출처 :  https://www.geeksforgeeks.org/heap-data-structure/ > 

---

파이썬 힙 자료구조

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

 

모든 부모 노드는 그의 자식 노드보다 값이 크거나 작은 바이너리 트리(이진트리) 구조이다.

 

0의 인덱스를 시작으로 k번재 원소가 항상 그의 자식원소인 2k + 1, 2k + 2 보다 작거나 같은 최소 힙 형태로 정렬된다.

 

heapq 모듈은 별도의 설치 없이 import 를 통해 바로 사용할 수 있다.

 

 

힙 관련 함수

• heapq.heappush(heap, num) : heap에 num을 추가한다.
• heapq.heappop(heap) : heap에서 가장 작은 원소를 빼고 지운다. 즉 pop 하며 리턴한다. 비어있는 경우 index 에러가 발생한다.
• heapq.heapify(x) : 리스트인 x를 heap르로 변환해준다.

 

 

# heapq.heappush ( ) 

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 100)
>>> heapq.heappush(heap, 30)
>>> heapq.heappush(heap, 50)
>>> heap
[30, 100, 50]

 

위 코드는 heap 이라는 빈 리스트에 100, 30, 50을 각각 추가하는 예시이다.

부모노드가 30이 되고 왼쪽과 오른쪽에 각각 100, 50이 들어간 이진트리 형태를 보여주고 있다.

 

# heapq.heapify( )

>>> heap = [100, 30, 50]
>>> heapq.heapify(heap)
>>> heap
[30, 100, 50]

 

사전에 생성해둔 리스트가 있다면 해당 리스트를 힙 자료형으로 바로 바꿀 수 있다.

 

 

# heapq.heappop ( )

>>> heap
[30, 100, 50]

>>> min_num = heapq.heappop(heap)
30

>>> heap
[50, 100]

 

heappop 함수는 힙에서 가장 작은 원소를 리턴하며 힙에서 삭제한다.

위 코드의 경우 30이 힙에서 삭제되면서 50이 부모노드로 바뀐 것을 확인할 수 있다.

 

최소값을 힙에서 삭제하지 않고 사용하고 싶다면 리스트에서 0번째 index를 호출하면 된다.

 

 

## 최대 힙

파이썬의 heapq 모듈은 최소힙을 만들기 때문에 최대힙을 만들기 위해선 새로 정렬을 해주는 방법이 필요하다.

 

힙에 원소를 추가할 때 (-num, num)의 형태의 튜플을 넣어주면 첫 번째 원소를 우선순위로 힙을 구성하게 된다.

 

이때 원소의 값의 부호를 바궜기 때문에 최소의 힙으로 구성되던 것이 최대 힙으로 구성이 되는 것이다.

 

>>> heap_list = [1,3,5,7,9]
>>> heap_max = []

>>> for num in heap_list:
		heapq.heappush(heap_max, (-num, num))

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

 

heappush 함수를 통해 heap_max에 힙을 push 할때 (-num, num) 형태로 넣은 것올 알 수 있다.

 

여기서 최대값을 출력하기 위해선 pop 함수와 함께 2번째 인덱스인 [1] 을 출력하면 최대값을 뽑아내며 사용할 수 있다.

 

위의 방법대로 하지 않고 새로운 리스트에 [1] 번의 수를 append 한다면 최대값을 뽑아 낸 후 자동으로 힙을 구성해주지 않기 때문에 올바른 방법이 아니다.