이진 힙: 맨 앞의 최솟값을 빠르게 유지하는 배열
이진 힙은 완전 이진 트리 형태와 힙 순서 조건을 가진 자료구조다. 최소 힙에서는 부모 값이 자식 값보다 작거나 같다. 그래서 루트가 전체 최솟값이다. 형제끼리나 서로 다른 가지 사이에는 정렬 조건이 없으므로 전체 배열이 정렬되어 있지는 않다.
최소 힙은 부모가 자식보다 크지 않도록 유지하며 배열 전체가 정렬된 것은 아니다.
트리를 배열로 저장하기
0부터 시작하는 배열에서 i의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2이고 부모는 (i-1)//2다. 마지막 층을 왼쪽부터 채우는 완전 트리이므로 빈칸 없이 배열로 표현할 수 있다. 명시적인 노드 포인터가 필요하지 않다.
새 값은 배열 끝에 추가한다. 부모보다 작으면 교환하며 올라가는 sift-up을 수행한다. [2,5,7,9]에 1을 넣으면 먼저 부모 5와, 다시 루트 2와 교환하여 조건을 복구한다. 영향을 받는 것은 새 원소부터 루트까지의 경로다.
최솟값 제거 뒤에는 내려간다
루트 값을 저장하고 마지막 값을 루트로 옮긴 다음 더 작은 자식과 비교해 내려보낸다. 두 자식 중 큰 쪽과 교환하면 다른 작은 자식 때문에 조건이 여전히 깨질 수 있다.
def sift_down(values, start_index):
parent = start_index
size = len(values)
while 2 * parent + 1 < size:
smaller_child = 2 * parent + 1
right_child = smaller_child + 1
if right_child < size and values[right_child] < values[smaller_child]:
smaller_child = right_child
if values[parent] <= values[smaller_child]:
break
values[parent], values[smaller_child] = values[smaller_child], values[parent]
parent = smaller_child
높이가 O(log n)이므로 삽입과 최소 제거는 O(log n), 최소 확인은 O(1)이다. 임의의 값 검색은 힙 조건만으로 한 가지를 골라 갈 수 없어 O(n)이 걸릴 수 있다. 이진 탐색 트리처럼 순서 검색이 되는 구조가 아니다.
배열 전체를 힙으로 만드는 과정은 마지막 내부 노드부터 sift-down하면 O(n)이다. 모든 노드가 log n만큼 내려가는 것이 아니라 대부분은 잎 근처에 있어 이동할 높이가 작다. n번 순차 삽입의 O(n log n) 상한과 구분해야 한다.
힙은 우선순위 큐, 상위 k개 선택, 힙 정렬에 쓰인다. 동일 우선순위의 삽입 순서를 보존하려면 별도 순번을 비교 키에 넣어야 한다. 저장한 원소의 우선순위를 외부에서 직접 바꾸면 힙 조건이 깨질 수 있으므로 변경 뒤 재정렬하는 API가 필요하다.
우선순위 감소를 자주 지원하려면 항목의 배열 위치를 함께 관리할 수 있다. 원소를 교환할 때마다 위치 맵도 갱신해야 다음 변경이 올바른 곳에서 sift-up을 시작한다.