부산대학교자료구조
Scientific Inference Lab

Up and Down One Level

Heapify

heapify(임의의 배열을 힙으로 만들기)는 단말 노드를 그대로 두고, 마지막 부모부터 루트까지 거꾸로 가며 각 자리에서 sift down을 한 번씩 한다. 아래쪽 부분 트리가 이미 힙이므로 한 번의 sift down으로 충분하고, 노드가 많은 아래 레벨일수록 내려갈 거리가 짧아 전체 비용이 O(n)이다.

시작 위치인덱스 ⌊n/2⌋ − 1이 마지막 부모이고, 그 뒤는 모두 단말 노드라 이미 힙이다.
아래에서 위로i에서 sift down할 때 i의 두 부분 트리는 이미 힙이므로 i 자리의 값 하나만 제자리로 보내면 된다.
n번 삽입과의 차이값을 하나씩 heappush하면 O(n log n), heapify는 O(n)이다. 결과 배열은 다를 수 있지만 둘 다 힙이다.

마지막 부모부터 거꾸로 sift down하면 아래쪽부터 힙이 되어 올라간다

배열 [9, 5, 6, 2, 3, 8, 1, 7, 4]를 heapify한다. 진행한 단계를 옮기면 sift down 중인 자리, 비교하는 자식 노드, 이미 힙이 된 부분이 바뀐다.

heapify 단계sift down 중인 자리와 이미 힙이 된 부분
초록으로 채운 원과 칸이 sift down 중인 값, 초록 테두리가 비교하는 자식 노드다. 옅은 파란 원과 칸은 그 자리를 루트로 하는 부분 트리가 이미 힙이 된 곳이고, 흰 원은 아직 처리하지 않은 부모다. 빨간 선은 아직 힙 성질을 어긴 간선이다.

같은 값으로 만들어도 방법에 따라 배열이 달라지고 둘 다 힙이다

같은 9개 값을 하나씩 heappush하는 방법과 heapify로 한꺼번에 만드는 방법을 비교한다. 방법을 바꾸면 결과 트리와 배열, 교환 횟수가 바뀐다.

두 방법의 결과 힙결과 트리와 배열
위는 결과 힙의 트리, 아래는 배열이다. 옅은 파란 칸은 두 방법의 결과가 같은 인덱스, 흰 칸은 다른 인덱스다.

노드가 많은 레벨은 내려갈 거리가 짧아 heapify의 총이동 횟수 상한이 n에 비례한다

높이 h인 가득 찬 완전 이진트리를 생각한다. 높이를 바꾸면 레벨마다의 노드 수, heapify에서 내려갈 수 있는 최대 거리, n번 삽입에서 올라갈 수 있는 최대 거리의 합이 바뀐다.

레벨별 노드 수와 이동 거리레벨마다 노드 수, heapify 거리, 삽입 거리
한 줄이 레벨 하나다. 파란 막대는 그 레벨의 노드 수, 초록 막대는 heapify에서 그 레벨 노드들이 내려갈 수 있는 거리의 합(노드 수 × 아래 레벨 수), 회색 막대는 n번 삽입에서 올라갈 수 있는 거리의 합(노드 수 × 깊이)이다. 막대 길이는 모든 레벨의 세 값 가운데 가장 큰 값을 기준으로 맞췄다.