힙 정렬

[출처 : http://blog.naver.com/holywater86/50098589686]

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);    } }