github
최소힙 자료구조란? 완전이진트리 (포화이진트리와 헷갈리지 말자) 로 구성된 자료구조. 부모 노드값이 자식 노드의 값보다 작게 트리를 구성한다. 그래서 트리의 루트 노드는 입력한 값들 중 최소값이 저장된다. 동작 방식 힙에 자료가 push되었을 경우 "업 힙" 동작을 한다. 부모와 비교하며 자식이 작을 경우 swap한다. 힙에서 자료가 pop되었을 경우 "다운 힙" 동작을 한다. 자식과 비교하며 자식이 클 경우 swap한다. 가장 깊은 레벨의 노드(7)가 루트로 올라간다는 점에 유의. 파이썬에서 자료구조 구현 heapq 자료구조를 import하여 간단하게 구현 가능하다. import heapq as hq heap = [] hq.heappop(heap) # 루트 노드의 값을 pop시킨다. hq.heappus..
