힙 알고리즘

힙은 모든 부모노드가 자식보다 같거나 작은 값을 갖는 완전 이진트리 이다.

최대 힙은 자식의 키 값보다 크거나 같은 값을 가지고, 최소 힙은 자식의 키 값보다 작거나 같은 값을 가진다.

 

모든 K에 대하여 heap[k] <-- heap[2*k +1], heap[k] <-- heap[2*k + 2]인 배열로 표현 할 수 있고,

존재하지 않는 요소는 무한대로 간주하며, 힙의 가장 작은 요소는 heap[0]이다.

 

2075번 문제를 풀면서 썻던 python의 heapq에 대해서

heappush는 힙의 불변성을 유지하면서 item 값을 heap에 넣어주는 함수이고,

heappop은 힙의 불변성을 유지하면서 가장 작은 값을 반환 해주는 함수인데, heap이 비어있으면 IndexError 가 발생한다. pop 없이 가장 작은 항목에 엑세스 하려면 heap[0]을 사용해도 된다.

 

 

 

출처: https://docs.python.org/ko/3/library/heapq.html