nlogn's log :: 천천히 달리기

6. 힙정렬

1) 힙 성질을 만족하는 완전 이진 트리 (마지막 층은 왼쪽부터 채워져 있으며 일부는 빌 수 있다.)

2) 힙

- 최소(대)힙 : 각 노드의 값이 자식보다 작(크)거나 같다

- root 값이 최소(대) 값이며, O(1) 에 검색이 가능하다.

- 바닥에 최대(소) 값이 존재 한다

3) 트리

- 가족관계 : 부모와 자식이 존재

- 원소갯수가 n일 경우 깊이는 logn

- 수행시간은 깊이에 비례한다.

4) 완전 이진 트리의 배열 표현

- A[k]의 왼쪽 자식 : A[2k]

- A[k]의 오른쪽 자식 : A[2k+1]

- A[k]의 부모 : A[ k/2의 내림값 ]

5) 수행시간 : O(nlogn)

6)

heapSort(A, n)
{
buildHeap(A, n); // 힙을 만든다
for i ← n downto 2  // 참조구역 조정

   {
   A[1] ↔ A[i]; // 역배열, 참조 안하는 구역의 값과 교환
   heapify(A, 1, i-1); // 힙 조건을 만족시킨다.
   }
}

buildHeap(A[], n)
{
   for i ←⌊n/2⌋ downto 1 //최초 자식을 가지는 놈 찾기
   heapify(A, i, n);
}

Heapify(A[], k, n)
{
   left ← 2k; right ← 2k+1;
   if(right ≤ n) // 작은값 찾기

   {
      if(A[left] < A[right]) // 자식이 둘 인 경우

         smaller ← left;
      else smaller ← right
   }
   else if (left ≤ n)

      smaller ← left; // 왼쪽자식만 있는 경우
   else return; // 자식이 없는 경우

   if(A[smaller] < A[k]) //재귀적으로 가장 작은 값을 정점과 바꿔 힙 성질을 만족 시킨다.

   {
      A[k] ↔ A[smaller];
      heapify(A, smaller, n);
   }
}