힙 (heap)

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

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)