안녕하세요. 이번 포스트에서는 힙정렬에 관해 알아보겠습니다. 힙과 힙정렬이 무엇인지 알아보고 힙정렬 예제 코드도 보여 드리도록 하겠습니다.
힙 정렬의 정의
힙 정렬(heap sort)은 힙이라는 구조를 사용하여 숫자들을 크기 순서대로 정렬하는 방법을 말합니다.
힙(heap)은 특별한 규칙을 가진 나무 모양의 구조입니다. 그 규칙이란 부모 노드가 자식 노드보다 크거나 같아야 하는 것인데, 이런 힙을 최대 힙(max heap)이라고 합니다. 반대로 부모 노드가 자식 노드보다 작거나 같아야 하는 힙을 최소 힙(min heap)이라고 합니다.
힙 정렬의 기본 동작 방법
힙 정렬은 다음과 같은 과정을 거칩니다:
1. 먼저, 주어진 숫자들로 최대 힙을 만듭니다. 이렇게 하면 가장 큰 숫자가 힙의 꼭대기(루트)에 위치하게 됩니다.
2. 그 다음, 힙의 꼭대기에 있는 가장 큰 숫자를 빼내어 (이를 '삭제'라고 합니다) 배열의 맨 끝에 놓습니다.
3.이제 힙에는 하나의 숫자가 적게 되었고, 가장 큰 숫자는 배열의 맨 끝에 위치하게 됩니다.
4. 그런 다음, 남은 힙을 다시 조정하여 최대 힙의 형태를 유지합니다. 이렇게 하면 이번에는 두 번째로 큰 숫자가 힙의 꼭대기에 오르게 됩니다.
5. 2~4의 과정을 반복하면, 숫자들이 큰 순서대로 배열의 끝에서부터 차례로 놓이게 됩니다. 이렇게 하면 최종적으로 배열의 숫자들이 작은 순서대로 정렬되게 됩니다.
힙정렬 예제코드
그럼 실제 코드 예제를 통해 힙 정렬의 실제 구현 방법을 알아보겠습니다.
#include <stdio.h> // 기본적인 입출력 기능을 사용하기 위한 라이브러리
#include <stdlib.h> // 메모리 할당 등의 기능을 사용하기 위한 라이브러리
#define MAX_ELEMENT 200 // 힙이 가질 수 있는 최대 요소 수를 정의
// 정렬하려는 숫자를 저장하는 구조체
typedef struct {
int key; // 정렬하려는 숫자
}element;
// 최대 힙을 나타내는 구조체
typedef struct {
element heap[MAX_ELEMENT]; // 힙에 저장된 요소들
int heap_size; // 힙의 현재 크기
}HeapType;
// 힙을 생성하고 초기화하는 함수
HeapType* create()
{
return (HeapType*)malloc(sizeof(HeapType)); // 힙을 위한 메모리 공간을 할당
}
// 힙을 초기화하는 함수
void init(HeapType* h)
{
h->heap_size = 0; // 힙의 크기를 0으로 설정
}
// 최대 힙에 요소를 삽입하는 함수
void insert_max_heap(HeapType* h, element item)
{
int i;
i = ++(h->heap_size); // 삽입할 위치를 힙의 마지막으로 설정
// 삽입하려는 요소가 부모 노드보다 크다면 계속해서 부모 노드와 위치를 바꿈
while ((i != 1) && (item.key > h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item; // 요소를 삽입
}
// 최대 힙에서 가장 큰 요소를 삭제하고 반환하는 함수
element delete_max_heap(HeapType* h)
{
int parent, child;
element item, temp;
item = h->heap[1]; // 힙의 루트에 있는 가장 큰 요소를 저장
temp = h->heap[(h->heap_size)--]; // 힙의 마지막 요소를 임시로 저장
parent = 1;
child = 2;
// 삭제된 루트 노드에 대한 새로운 위치를 찾아 재조정
while (child <= h->heap_size) {
// 두 자식 노드 중에서 더 큰 자식 노드를 선택
if ((child < h->heap_size) &&
(h->heap[child].key) < h->heap[child + 1].key)
child++;
if (temp.key >= h->heap[child].key)break; // 재조정 완료
h->heap[parent] = h->heap[child];
// 한 단계 아래로 이동
parent = child;
child *= 2;
}
h->heap[parent] = temp; // 임시로 저장한 요소를 새 위치에 삽입
return item; // 가장 큰 요소를 반환
}
// 힙 정렬을 수행하는 함수
void heap_sort(element a[], int n)
{
int i;
HeapType* h;
h = create(); // 새 힙을 생성
init(h); // 힙을 초기화
// 배열의 모든 요소를 힙에 삽입
for (i = 0; i < n; i++) {
insert_max_heap(h, a[i]);
}
// 힙에서 요소를 하나씩 삭제하여 배열에 반대 순서로 저장
for (i = (n - 1); i >= 0; i--) {
a[i] = delete_max_heap(h);
}
free(h); // 힙에 할당된 메모리를 해제
}
#define SIZE 8 // 정렬할 숫자의 개수를 정의
// 프로그램의 시작점
int main(void)
{
// 정렬하려는 숫자들을 저장한 배열
element list[SIZE] = { 23,56,11,9,56,99,27,34 };
heap_sort(list, SIZE); // 힙 정렬을 수행
// 정렬된 결과를 출력
for (int i = 0; i < SIZE; i++) {
printf(" %d", list[i].key);
}
printf("\n"); // 줄바꿈 문자를 출력
return 0; // 프로그램을 종료
}
실행결과는 아래와 같습니다.
댓글