히프 정렬 (Heap Sorting)

히프는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다.

최소 히프와 최대 히프가 있고 정렬에서는 최소 히프를 사용하는 것이 프로그램이 더 쉽다.

최소 히프는 부모 노드의 값이 자식 노드의 값보다 작기 때문에 최소 히프의 루트 노드는 가장 작은 값이다.

이러한 특성을 이용하여 정렬할 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법이다.

히프는 1차원 배열로 쉽게 구현될 수 있다.

최소 히프를 만들고 숫자들을 차례대로 삽입한 다음 최솟값(root)부터 삭제하면 된다.

최소 히프는 작은 값이 root고 이것부터 뽑아 내므로 오름차순 정렬,

최대 히프는 큰 값이 root이고 이것부터 뽑아 내므로 내림차순 정렬에 해당한다.

여기서는 최대 히프 정렬(내림차순 정렬)을 사용한다.

맨 아래쪽에 최소 히프 정렬(오른차순 정렬)의 소스도 있으니 참고하면 된다.

n개의 요소는 시간 안에 정렬된다.

1. 정렬해야 할 n개의 요소들로 최대 히프를 초기화

2. 하나씩 요소를 히프에서 꺼내서 배열의 뒤부터 저장한다.

   -> 삭제되는 요소들은 값이 감소되는 순서로 정렬된다.

히프 트리의 전체 높이가 거의 이므로(완전 이진 트리) 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 만큼 소요된다. 

요소의 개수가 n개이므로 전체적으로 의 시간이 걸린다.

이 시간 복잡도는 삽입 정렬같은 간단한 정렬 알고리즘이 의 시간이 걸리는 것에 비하면 좋은 편이다.

히프 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.

히프정렬의 코드는 다음과 같다.

0번 인덱스는 사용하지 않으므로 인덱스 변수는 1부터 시작해야하고, size변수 인덱스값 까지 반복해야한다.

// 우선순위 큐인 히프를 이용한 정렬
void heap_sort(int list[], int size) {
    HeapType h;
    init(&h);

    for (int i = 1; i <= size; i++)
    insert_max_heap(&h, list[i]);

    for (int i = size; i > 0; i--)
    list[i] = delete_max_heap(&h);
    }

전체 프로그램

MAX_SIZE개의 난수를 발생, 배열 list에 저장. 난수의 발생 범위는 0~MAX_SIZE-1까지이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10

typedef struct {
    int heap[MAX_SIZE + 1];
    int heap_size;
} HeapType;

// 삭제 함수
    int delete_max_heap(HeapType *h) {
    int parent = 1, child = 2;
    int item, tmp;

    item = h->heap[1];
    tmp = h->heap[(h->heap_size)--];

    while (child <= h->heap_size) {
        //현재 노드의 자식 노드 중 더 큰 자식 노드를 검색
        if ((child < h->heap_size) && (h->heap[child]) < h->heap[child + 1])
            child++;
    
    
        if (tmp >= h->heap[child]) break;
    
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }

    h->heap[parent] = tmp;
    return item;
}

// 초기화 함수
void init(HeapType *h) {
    h->heap_size = 0;
}

// 삽입함수
void insert_max_heap(HeapType *h, int item) {
    int i = ++(h->heap_size);

    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while ((i != 1) && (item > h->heap[i / 2])) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }

    h->heap[i] = item; // 새로운 노드 삽입
}

// 우선순위 큐인 히프를 이용한 정렬
void heap_sort(int list[], int size) {
    HeapType h;
    init(&h);

    for (int i = 1; i <= size; i++)
        insert_max_heap(&h, list[i]);

    for (int i = size; i > 0; i--)
        list[i] = delete_max_heap(&h);
}

void main() {
    int list[MAX_SIZE];

    printf("<최대히프정렬 - 내림차순>\n정렬 이전 배열 : ");
    for (int i = 1; i <= MAX_SIZE; i++) {// 난수 생성 및 출력
        list[i] = rand() % MAX_SIZE; // 난수 발생범위 0 ~ n
        printf("%d ", list[i]);
    }
    printf("\n");

    heap_sort(list, MAX_SIZE); // 히프 정렬 호출

    printf("최종 정렬 결과 : ");
    for (int i = MAX_SIZE; i > 0; i--)
        printf("%d ", list[i]);

    printf("\n");
    system("pause");
}

 

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 40000

typedef struct {
    int heap[MAX_SIZE + 1];
    int heap_size;
} HeapType;

// 삭제 함수
int delete_max_heap(HeapType *h) {
    int parent = 1, child = 2;
    int item, tmp;
    
    item = h->heap[1];
    tmp = h->heap[(h->heap_size)--];
    
    while (child <= h->heap_size) {
        //현재 노드의 자식 노드 중 더 큰 자식 노드를 검색
        if ((child < h->heap_size) && (h->heap[child]) < h->heap[child + 1])
            child++;
        
        
        if (tmp >= h->heap[child]) break;
        
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    
    h->heap[parent] = tmp;
    return item;
}

// 초기화 함수
void init(HeapType *h) {
    h->heap_size = 0;
}

// 삽입함수
void insert_max_heap(HeapType *h, int item) {
    int i = ++(h->heap_size);
    
    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while ((i != 1) && (item > h->heap[i / 2])) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    
    h->heap[i] = item; // 새로운 노드 삽입
}

// 우선순위 큐인 히프를 이용한 정렬
void heap_sort(int list[], int size) {
    HeapType h;
    clock_t start = clock(); // 시간재기 시작
    init(&h);
    
    for (int i = 1; i <= size; i++)
        insert_max_heap(&h, list[i]);
    
    for (int i = size; i > 0; i--)
        list[i] = delete_max_heap(&h);
    
    
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("히프정렬\n크기 : 40000개\n%.4lf초", diff);
}

void main() {
    int list[MAX_SIZE];
    
    for (int i = 1; i <= MAX_SIZE; i++)// 난수 생성 및 출력
    list[i] = rand() % MAX_SIZE; // 난수 발생범위 0 ~ n
    
    heap_sort(list, MAX_SIZE); // 히프 정렬 호출
    
    printf("\n");
    system("pause");
}

 

히프의 삽입과 삭제 연산의 시간 복잡도를 분석한다.

삽입 연산에서 새로운 요소 히프 트리를 타고 올라가면서 부모 노드들과 교환을 하게 되는데, 최악의 경우 루트 노드까지 올라가야 하므로 거의 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다.

히프가 완전 이진 트리임을 생각하면 히프의 높이는 가 되고, 따라서 삽입 연산의 시간 복잡도는 가 된다.

삭제도 마찬가지로 마지막 노드를 루트로 가져온 후에 자식 노드들과 비교하여 교환하는 부분이 가장 시간이 걸리는 부분인데,

이 역시 최악의 경우 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이만큼의 시간이 걸린다.

따라서 삭제 연산의 시간복잡도도 이 된다.

 

최소 히프 정렬과 최대 히프 정렬은 삽입/삭제의 코드에서 부등호만 조금 바꾸면 된다.

최대 히프와는 다르게 작은 값이 root가 되고, 큰 값들은 자식이 된다.

삭제 시에도 마찬가지이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10

typedef struct {
    int heap[MAX_SIZE + 1];
    int heap_size;
} HeapType;

// 삭제 함수
int delete_min_heap(HeapType *h) {
    int parent = 1, child = 2;
    int item, tmp;
    
    item = h->heap[1];
    tmp = h->heap[(h->heap_size)--];
    
    while (child <= h->heap_size) {
    
        //현재 노드의 자식 노드 중 작은 자식 노드를 검색
        if ((child < h->heap_size) && (h->heap[child]) > h->heap[child + 1])
            child++;
        
        if (tmp < h->heap[child]) break;
        
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    
    h->heap[parent] = tmp;
    return item;
}

// 초기화 함수
void init(HeapType *h) {
    h->heap_size = 0;
}

// 삽입함수
void insert_min_heap(HeapType *h, int item) {
    int i = ++(h->heap_size);
    
    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while ((i != 1) && (item < h->heap[i / 2])) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    
    h->heap[i] = item; // 새로운 노드 삽입
}

// 우선순위 큐인 히프를 이용한 정렬
void heap_sort(int list[], int size) {
    HeapType h;
    init(&h);
    
    for (int i = 1; i <= size; i++)
        insert_min_heap(&h, list[i]);
    
    for (int i = size; i > 0; i--)
        list[i] = delete_min_heap(&h);

}

void main() {
    int list[MAX_SIZE];
    
    printf("<최소히프정렬 - 오름차순>\n정렬 이전 배열 : ");
    
    for (int i = 1; i <= MAX_SIZE; i++) {// 난수 생성 및 출력
        list[i] = rand() % MAX_SIZE; // 난수 발생범위 0 ~ n
        printf("%d ", list[i]);
    }
    
    printf("\n");
    
    heap_sort(list, MAX_SIZE); // 히프 정렬 호출
    
    printf("최종 정렬 결과 : ");
    
    for (int i = MAX_SIZE; i > 0; i--)
        printf("%d ", list[i]);
    
    printf("\n");
    system("pause");
}