Heapify의 시간복잡도는 O(n)이다!

• heapify는 O(logN)의 작업을 N 번 하니까 여느 sort처럼 O(NlogN)이 걸릴 것 같지만 그렇지 않다.
• heapify한 heap을 이용해 배열로 만드는 시간 (heap-build)가 O(NlogN)이 걸리는 것이다.

레퍼런스

요약

• 각 노드들이 최대 얼마나 움직일 수 있는지를 기준으로 정해진다.
• 각 노드들은 연산시 아래쪽으로만 이동한다. (재귀적인 heapify)
• 각 높이에 있는 노드들은 최악의 경우에 h번 swap을 한다. (꼭대기에서 바닥까지 가는 경우)
• 각 높이에 있는 노드는 대략 n/2^h개 이다. (2^h개의 노드를 가정했을 때, 꼭대기층에는 1개, 그 아래층에는 2개..)
• 이 식을 시그마하면 O(n)이 된다.

설명

heapify의 과정

heapify 적용 순서

• 위와 같이 맨 마지막 비 리프부터 시작해서, 윗쪽 노드로 가면서 heapify를 수행한다.

• heapify의 과정 
  • 두 자식 노드 중 나보다 더 큰 노드가 있으면 걔랑 자리 바꾼다. (두 노드 중 더 큰 쪽과 바꾼다)
  • 교환이 됐다면 바꾼 위치에서 heapify를 다시 한번 한다.
  • 교환이 안 되거나 바닥에 내려갈 때까지 반복한다.
  • 즉 최대 h 번 교환된다.

• 예를 들면 다음과 같이 진행된다.

heapify 예

• 각 레벨 h에 있는 노드는 n/2^h 개이므로 다음과 같이 식을 세울 수 있다.

T = Σ (from h=0 to h=log(n)) [n / 2^(h+1)];

• Big O (n이 무한으로 갈 때) 에서 아래와 같이 근사할 수 있다.

T = Σ (from h=0 to h=log(n)) [n / 2^(h+1)] * O(h)
  = n * Σ (from h=0 to h=infinite) [h / 2^(h)];

뒷쪽 시그마는 계산하면 2가 된다. (기하급수 일반 합공식을 통해 구할 수 있다. 최종적으로 T = 2n 이고, Big O 로는 O(n)이다.

배운 것

• 공부하면서 어려워보이던 기하급수 일반 합공식도 내가 원래 알던거라는걸 깨닫게 되었다.
• heap도 다시 시뮬레이션해 볼 수 있어 좋았다.