▶ Heapify 구현
node i에 대하여 heapify 함수를 적용하면, node i의 subarray는 max-heap property를 만족하게 된다.
void heapify(int A[], int i, int n) {
int largest;
if (2*i <= n && A[2*i] > A[i])
largest = 2*i;
else
largest = i;
if (2*i+1 <= n && A[2*i+1] > A[largest])
largest = 2*i+1;
if (largest != i) {
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
heapify(A, largest, n);
}
}
1. node i와 왼쪽 자식 비교
- node 2i가 존재하고, 그 값이 부모인 node i의 값보다 클 경우, largest <- 2i
- 그렇지 않은 경우(node 2i가 존재하지 않거나, 존재하더라도 그 값이 node i의 값보다 작은 경우), largest <- i
2. node largest와 오른쪽 자식 비교
- node 2i+1이 존재하고, 그 값이 node largest(node i와 node 2i 중 더 큰 값을 가지는 node)의 값보다 클 경우, largest <- 2i+1
3. 만일 largest가 i가 아닐 경우
- node i와 node 2i, node 2i+1 중 가장 큰 값을 가지는 node largest가 node i가 아니면, max-heap의 특성을 만족시키기 위해 node i와 node largest의 자리를 exchange
- 교환된 node에 재귀적으로 heapify를 호출하여 float down 방식으로 heap property를 만족시키며 max-heap을 완성
> test
int main() {
int A[11] = {0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
heapify(A, 2, 10);
for (int i=0; i<11; i++) {
printf("%d ", A[i]);
}
return 0;
}
> result
▶ BuildHeap 구현
buildHeap은 정렬되지 않은 배열 A가 주어졌을 때, 배열 A를 max-heap으로 만들어주는 함수이다.
void buildHeap (int A[], int n) {
for (int i=n/2; i>=1; i--)
heapify(A, i, n);
}
- 배열의 크기가 n일 때, leaf node들인 A[n/2+1], A[n/2+2], …, A[n]은 이미 max-heap이다. 노드가 하나뿐인 subarray이기 때문이다.
- 따라서 internal node들인 A[1], A[2], …, A[n/2]들의 subarray만 heap property를 만족하게 해주면 된다.
- A[n/2]부터 A[1]까지 bottom-up 방식으로 heapify()를 실행시켜주면 전체 배열이 max-heap된다.
> test
int main() {
int A[11] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
buildHeap(A, 10);
for (int i=0; i<11; i++) {
printf("%d ", A[i]);
}
return 0;
}
> result
▶ HeapSort 구현
heapSort는 heap data structure를 이용하여 정렬되지 않은 배열 A가 주어졌을 때, 배열 A를 작은 값부터 큰 값 순서대로 정렬시켜주는 함수이다.
void heapSort (int A[], int n) {
buildHeap(A,n);
for (int i=n; i>=2; i--) {
int temp = A[1];
A[1] = A[i];
A[i] = temp;
heapify(A, 1, i-1);
}
}
1. 배열 A에 buildHeap()을 호출하여 max-heap으로 만든다.
2. root인 A[1]에 있는 가장 큰 원소를 배열의 마지막 원소와 바꾼다.
3. 가장 큰 값으로 바뀐 배열의 마지막 원소를 heap에서 해방시킨다.
4. A[1]만이 heap property를 만족하지 않기 때문에 A[1]을 대상으로 heapify()를 호출하여 다시 max-heap으로 만든다.
5. heapify()의 대상이 되는 원소가 하나씩 줄어든다. 다시 말해, 힙 정렬이 완료된 원소가 하나 늘어나는 것이다.
6. n이 2가 될 때까지 이 과정을 반복한다. heap에 남아있는 원소의 개수가 하나가 되면 힙 정렬 수행이 끝난다.
> test
int main() {
int A[11] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
buildHeap(A, 10);
for (int i=0; i<11; i++) {
printf("%d ", A[i]);
}
return 0;
}
> result
