1-1. 힙 자료구조
- 완전 이진트리 중 하나 -> 웃너순위 큐를 위해 만들어진 자료구조
- 여러개의 값들 중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
- 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음)
- heapq 모듈은 이진트리 기반의 최소힙 자료구조를 제공한다.
1-2. 힙 종류
- 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 완전 이진트리
- 가장 큰 값은 언제나 index = 0에 위치함 (=> 이진트리의 루트에 위치)
heap[k] >= heap[2*k+1] and heap[k] >= heap[2*k+2]
- 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 값보다 작거나 같은 완전이진트리
- 가장 작은 값은 언제나 index = 0에 위치함 (=> 이진트리의 루트에 위치)
heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]
2-1. 힙 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다
- 구현을 쉽게하기 위해 idx=0은 사용하지 않는다.
- 특정 위치의 노드번호는 새로운 노드가 추가되어도 변하지 않는다.
- 힙에서의 부모노드와 자식 노드의 관계
- 왼쪽 자식 index = (부모 index) * 2
- 오른쪽 자식 index = (부모 index) * 2 + 1
- 부모 index = (자식 index) / 2
2-2. 힙의 삽입
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어 삽입한다.
- 새로운 노드를 부모 노드들과 교환해서 힙의성질을 만족시킨다.
- O(logN)
2-3. 힙의 삭제
- 최대 힙에서 최댓값은 루트 노드이므로 루트노드가 삭제된다.
- O(logN)
2-3. list를 힙으로 변환
3-1. list를 힙으로 변환
- heapq묘듈은 최소 힙 기능만을 동작한다.
- 최대 힙을 활용하려면 힙에 튜플을 원소로 추가하거나 삭제하면 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리 이용
- 최대 힙을 만들기 위해서는
- 1. 각 값에 대한 우선순위 구하기
- 2. (우선순위, 값) 구조의 튜플을 힘에 추가하거나 삭제
- 3. 값을 읽어올 때는 튜플에서 인덱스1에 있는 값을 뽑아오면 된다.
3-2. 힙 정렬
3-3. K번째 최솟값 / 최댓값
