heapq

힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..