[Introduction to Algorithms] 힙 특성 유지하기

 

1) 최대 힙 특성 유지하기 

 

- 최대 힙 특성을 유지하기 위해 MAX-HEAPIFY가 호출된다. 입력은 배열 A와 배열의 인덱스 i다.  

  MAX-HEAPIFY를 호출할 때 LEFT(i)와 RIGHT(i)를 루트로 하는 이진 트리가 최대 힙이라고 가정하는데,

  A[i]가 자식들보다 작아 최대 힙 특성에 어긋나는 일이 생길 수 있다.

  MAX-HEAPIFY 프로시저는 최대 힙에서 A[i] 값을 "내려보냄"으로써, 

  인덱스 i를 루트로 하는 서브 트리가 최대 힙이 되도록 한다. 

MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l<= A.heap-size and A[l] > A[i]
   largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest] 
   largest = r
if largest != i
   exchange A[i] with A[largest] 
   MAX-HEAPIFY(A, largest)

 

- 위의 그림은 MAX-HEAPIFY의 동작을 설명한다. 

   각 단계에서 A[i], A[LEFT(i)], A[RIGHT(i)] 중 최대 원소가 정해지고 인덱스를 largest에 저장한다.

   A[i]가 최댓값이라면 노드 i를 루트로 하는 서브 트리는 최대 힙이므로 프로시저를 종료한다.

   그렇지 않으면 두 자식 중 최대 원소가 있으므로, A[i]를 A[largest]와 교환하여

   노드 i와 그 자식이 최대 힙 특성을 만족하게 한다. 

 

- 그러나 이제 largest번째 노드는 원래의 A[i] 값을 가지므로 largest를 루트로 하는 서브 트리가 최대 힙 특성과

   맞지 않을 수 있다. 

   따라서 MAX-HEAPIFY는 그 서브 트리로 재귀 호출되어야 한다. 

 

- 재귀 호출이 일어난다고 가정할 때 주어진 노드 i를 루트로 하고, 크기가 n인 서브 트리에서

  MAX-HEAPIFY의 수행시간은 원소 A[i], A[LEFT(i)], A[RIGHT(i)] 사이의 관계를 결정하는 

  시간 O(1)과 노드 i의 자식 중 하나를 루트로 하는 서브 트리에서 MAX-HEAPIFY를 실행하는 시간을 

  더한 것이다. 

 

- 자식들의 서브 트리는 최대 크기가 2n/3이다.

  따라서 MAX-HEAPIFY의 수행시간은 다음과 같은 재귀 관계식으로 나타낼 수 있다. 

T(n) <= T(2n/3) + O(1)