[Python] 최소힙(heap) 자료구조

최소힙 자료구조란?

완전이진트리 (포화이진트리와 헷갈리지 말자) 로 구성된 자료구조.

부모 노드값이 자식 노드의 값보다 작게 트리를 구성한다.

그래서 트리의 루트 노드는 입력한 값들 중 최소값이 저장된다.

 

 

동작 방식

힙에 자료가 push되었을 경우 "업 힙" 동작을 한다.

부모와 비교하며 자식이 작을 경우 swap한다.

 

 

힙에서 자료가 pop되었을 경우 "다운 힙" 동작을 한다.

자식과 비교하며 자식이 클 경우 swap한다.

가장 깊은 레벨의 노드(7)가 루트로 올라간다는 점에 유의.

 

 

파이썬에서 자료구조 구현

heapq 자료구조를 import하여 간단하게 구현 가능하다.

import heapq as hq

heap = []

hq.heappop(heap)    # 루트 노드의 값을 pop시킨다.
hq.heappush(heap, 1)    # a라는 리스트에 1이라는 값을 push한다.