[Introduction to Algorithms] 힙 만들기

1) 힙 만들기 과정 

 

- 배열 A[1...n]을 최대 힙으로 바꿀 경우, MAX-HEAPIFY 프로시저를 바닥에서부터 위로 올라가는 식으로 이용한다.

  (여기서 n = A.length). 

  BUILD-MAX-HEAP 프로시저에서 트리의 나머지 노드에 대해 MAX-HEAPFIY를 수행한다. 

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = [A.length/2] downto 1 
  MAX-HEAPIFY(A, i)

 

 

 

- 위 그림은 BUILD-MAX-HEAP 동작의 예를 보여준다.

   BUILD-MAX-HEAP이 정확하게 동작함을 보이기 위해 다음과 같은 루프 불변성을 이용한다. 

  

- 2-3행에 있는 for 루프에서 반복을 시작할 때마다 노드 i+1, i+2, ... n은 모두 최대 힙의 루트가 된다.

  이 불변식이 첫 번째 반복 전에 참인지, 각 반복이 불변식을 유지하는지, 루프가 끝날 때 

  불변식이 알고리즘의 정확성을 뒷받침해 주는지 보일 필요가 있다. 

 

(1) 초기 조건

- 첫 번째 반복 전에 i = [n/2]이다. 각 노드 [n/2]+1, [n/2]+2, ... , n은 리프므로

  이들은 모두 자명하게 최대 힙의 루트가 된다. 

 

(2) 유지 조건

- 각 반복에서 루프 불변성이 유지되는지를 보기 위해 노드 i의 인덱스보다 자식들의 인덱스가 

  크다는 점을 상기하자. 루프 불변성에 따라 자식들은 모두 최대 힙의 루트가 된다.

  이는 노드 i를 최대 힙의 루트로 만들기 위해 MAX-HEAPFIY(A, i)를 호출할 때 필요한 조건이다.

  게다가 MAX-HEAPIFY 호출은 노드 i+1, i+2, ... n이 모두 최대 힙의 루트라는 특성을 깨뜨리지 않는다.

  for 루프에서 i를 줄임으로써 다음 반복에서도 루프 불변성을 유지한다. 

 

(3) 종료 조건

- 종료할  때, i = 0이다. 루프 불변성에 따르면 노드 1,2,.... , n은 각각 최대 힙의 루프다.

  특히, 노드 1이 최대 힙의 루트가 된다. 

 

 

2) BUILD-MAX-HEAP 수행시간 상한 계산하기 

 

- BUILD-MAX-HEAP 수행시간의 상한은 간단히 계산할 수 있다.

  MAX-HEAPIFY를 한 번 호출할 때마다 O(lgn) 시간이 걸리고, 호출 횟수는 O(n)번이다.

  그러므로 수행시간은 O(nlgn)이다. 

  이 상한은 틀린 것은 아니지만 개선할 여지가 있다. 

 

- MAX-HEAPIFY의 수행시간이 노드의 높이에 따라 다르고 노드 대부분의 높이가 작다는 점을 고려하면

  좀 더 정확한 시간을 구할 수 있다.

  이 분석은 원소가 n개인 힙의 높이는 [lgn]이고, 높이가 h인 노드 수는 최대 n/2^h+1이라는 사실을 이용한다.

   

- 높이가 h인 노드에서 호출될 때 MAX-HEAPIFY의 수행시간은 O(h)다.

  

- BUILD-MAX-HEAP에서 3행의 MAX-HEAPIFY를 MIN-HEAPIFY로 바꾼 BUILD-MIN-HEAP 프로시저를 사용해

  최소 힙을 만들 수 있다. 

  BUILD-MIN-HEAP 프로시저는 정렬되지 않은 배열로부터 선형 시간에 최소 힙을 만들어 낸다.