Python - 힙(Heap)

1) 힙(Heap)의 특징

완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드를 제거한다.

* 최소 힙
(1) 루트 노드가 가장 작은 값을 가진다.
(2) 따라서 값이 작은 데이터가 우선적으로 제거된다.

* 최대 힙
(1) 루트 노드가 가장 큰 값을 가진다.
(2) 따라서 값이 큰 데이터가 우선적으로 제거된다. 

 

---

2) 최소 힙 구성 함수: Min-Heapify()

부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.

상향식의 예를 보면,

왼쪽 자식 트리를 보면 최소 힙을 만족하지 않는다. 이럴 때 Min-Heapify를 수행하면 다음과 같이 노드의 위치가 변경된다.

이후에 3, 4 노드의 위치로 바꿔주면 최소힙이 완성된다.

 

import sys
import heapq	# 힙 라이브러리 import
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    
    for i in iterable:	# 모든 원소 차례대로 힙에 삽입
    	heapq.heappush(h, i)
        
    for i in range(len(h)): # 삽입된 모든 원소를 차례대로 꺼내어 담기
    	result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
res = heapsort(arr)

for i in range(n):
	print(res[i])

 

이것이 최소힙을 구현하는 코드이다.

heapq를 import 해주면 heappush, heappop등의 함수를 사용할 수 있다.

 

 

출처: https://youtu.be/AjFlp951nz0