자료구조 힙(heap)이란?
먼저 완전 이진 트리 가 무엇인지 알아보자. 완전 이진 트리 는 데이터 루트(Root) 노드부터 시작해서 자식 노드가 왼쪽, 오른쪽 노드로 차근차근 들어가는 구조의 이진 트리 이다.
힙(heap) 은 이 완전 이진 트리를 이용하여 최솟값이나 최댓값을 빠르게 찾아낼 수 있는 자료구조이다.
힙(heap)의 종류
최대 힙(Max Heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
key(부모 노드) >= key(자식 노드)
최소 힙(Min Heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
key(부모 노드) <= key(자식 노드)
▪ 파이썬에서는 heap기능을 위해 라이브러리 제공함.
▪ PriorityQueue 보다 heap이 코딩테스트 환경에서 더 빠름.
▪ 파이썬의 힙은 최소 힙으로 구성되어 있음.(최대 힙을 제공하지 않음.)
▪ 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬됨.
▪ 보통 최소 힙 자료구조의 최상단 원소는 가장작은 원소임.
heapq.heappush( ): 힙에 원소 삽입.
heapq.heappop( ): 힙에서 원소 꺼낼 경우.
