1. Max Heap 소스
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
void print_arr(int arr[], int size)
{
int i = 0;
for( i = 1; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
void swap(int *arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void heap(int *arr, int n, int m)
{
int i;
int j, parent;
for( i = 2 * n; i <= m; i+=2) {
j = i;
parent = j/2; // this is parent
if(arr[j] < arr[j+1]) // this is children --> 자식 중에 큰 자식을 찾는다.
j++;
if( j == m+1)
j--;
while( arr[parent] < arr[j]) { // parent와 자식을 비교하여 자식이 크다면 바꿔준다.
swap(arr, parent, j);
j = parent;
if( j == 1)
break;
parent = j/2;
} // while
} // for(i)
}
int main(int argc, char **argv)
{
int arr[SIZE], i;
arr[0] = -1;
for( i = 1; i < SIZE; i++)
arr[i] = rand() % 100;
printf("------------ input data -------------\n");
print_arr(arr, SIZE);
for( i = SIZE - 1; i >= 1; i--) {
heap(arr, 1, i); // 제일 큰 놈을 제외한 나머지 요소들로 heapify한다.
swap(arr, 1, i); // 제일 큰 놈을 뒤로 보낸다. --> 제일 작은 놈을 앞으로 보낸다.
}
printf("------------ sorted data -------------\n");
print_arr(arr, SIZE);
return 0;
}
#include <stdlib.h>
#include <time.h>
#define SIZE 20
void print_arr(int arr[], int size)
{
int i = 0;
for( i = 1; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
void swap(int *arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void heap(int *arr, int n, int m)
{
int i;
int j, parent;
for( i = 2 * n; i <= m; i+=2) {
j = i;
parent = j/2; // this is parent
if(arr[j] < arr[j+1]) // this is children --> 자식 중에 큰 자식을 찾는다.
j++;
if( j == m+1)
j--;
while( arr[parent] < arr[j]) { // parent와 자식을 비교하여 자식이 크다면 바꿔준다.
swap(arr, parent, j);
j = parent;
if( j == 1)
break;
parent = j/2;
} // while
} // for(i)
}
int main(int argc, char **argv)
{
int arr[SIZE], i;
arr[0] = -1;
for( i = 1; i < SIZE; i++)
arr[i] = rand() % 100;
printf("------------ input data -------------\n");
print_arr(arr, SIZE);
for( i = SIZE - 1; i >= 1; i--) {
heap(arr, 1, i); // 제일 큰 놈을 제외한 나머지 요소들로 heapify한다.
swap(arr, 1, i); // 제일 큰 놈을 뒤로 보낸다. --> 제일 작은 놈을 앞으로 보낸다.
}
printf("------------ sorted data -------------\n");
print_arr(arr, SIZE);
return 0;
}
2. Min Heap 소스
Max Heap 소스에서 일부만 수정
for( i = 2 * n; i <= m; i+=2) {
j = i;
parent = j/2; // this is parent
if(arr[j] > arr[j+1]) // this is children --> 자식 중에 작은 자식을 찾는다.
j++;
if( j == m+1)
j--;
while( arr[parent] > arr[j]) { // parent와 자식을 비교하여 자식이 작다면 바꿔준다.
swap(arr, parent, j);
j = parent;
if( j == 1)
break;
parent = j/2;
} // while
} // for(i)
j = i;
parent = j/2; // this is parent
if(arr[j] > arr[j+1]) // this is children --> 자식 중에 작은 자식을 찾는다.
j++;
if( j == m+1)
j--;
while( arr[parent] > arr[j]) { // parent와 자식을 비교하여 자식이 작다면 바꿔준다.
swap(arr, parent, j);
j = parent;
if( j == 1)
break;
parent = j/2;
} // while
} // for(i)
'IT > 알고리즘' 카테고리의 다른 글
| 이진 검색 트리 (binary search tree) (0) | 2008.07.16 |
|---|---|
| 타 변수 없이 서로의 값을 치환하는 방법 (0) | 2008.07.16 |
| + integer 값을 - integer 값으로 바꾸는 가장 간단한 방법 (0) | 2008.07.16 |
| 하나의 소수(솟수)가 주어졌을때, 다음 소수(솟수)를 찾는 알고리즘 (0) | 2008.07.15 |
| qsort (퀵 정렬) - 재귀, 비재귀, 삽입정렬, 난수발생 (1) | 2008.07.15 |
쩐의시대
나답게 살아가고 나답게 살아가자