문돌이 존버/프로그래밍 스터디
2021. 6. 4.
힙(Heap) 자료구조 알아보기
힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다. 우선순위 큐를 구현할 때는 내부적으로 최소 힙(min heap) 또는 최대 힙(max heap)을 이용한다. 최소 힙은 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙은 '값이 큰 데이터가 먼저 삭제'된다. 파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도가 $O(NlogN)$에 오름차순 정렬이 완료된다. 데이터 개수가 N개일 때, 삽입 시 $O(logN)$의 연산을 N번 반복하므로 $..
