[자료구조] 힙(Heapq) 파이썬 모듈 사용

힙은 Min Heap과 Max Heap으로 나눌 수 있다. 힙은 세 가지 특징을 가진다. - Min Heap인 경우 루트노드가 항상 최소값, Max Heap인 경우 루트노드가 항상 최댓값을 가진다. - Max Heap(Min) 내의 임의의 노드를 루트로 하는 서브트리 또한 Max Heap(Min)이다. - 완전 이진 트리여야한다. 따라서 m 번 노드의 왼쪽 자식 노드는 2m+1번이고, 오른쪽 자식 노드는 2m+2번이다. 힙의 장점 삽입/삭제 연산이 BST보다 빠르다. 시간 복잡도는 O(log n)으로 동일하지만 힙은 무조건 완전이진트리이므로 모든 삭제/삽입 연산이 배열의 가장 끝에서 발생한다. heapq 모듈 사용 heapq 모듈은 이진트리(Binary tree) 기반의 최소 힙(min heap) 자료구..
Coding - Algo 2021. 4. 20. 16:00
1