[코딩테스트]힙

📖힙

완전 이진 트리의 일종, 우선순위 큐를 위해 만들어진 자료구조.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조.

최대 힙(Max Heap): 각 노드의 키 값이 그 자식노드의 키 값보다 큰 힙.
최소 힙(MIn Heap): 각 노드의 키 값이 그 자식노드의 키 값보다 작은 힙.

▪ 파이썬에서는 heap기능을 위해 라이브러리 제공함.
▪ PriorityQueue 보다 heap이 코딩테스트 환경에서 더 빠름.
▪ 파이썬의 힙은 최소 힙으로 구성되어 있음.(최대 힙을 제공하지 않음.)
▪ 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬됨.
▪ 보통 최소 힙 자료구조의 최상단 원소는 가장작은 원소임.

heapq.heappush( ): 힙에 원소 삽입.
heapq.heappop( ): 힙에서 원소 꺼낼 경우.

📒이것이 취업을 위한 코딩테스트다 with 파이썬 책을 참고하여 작성하였습니다.
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661