[C/자료구조] 최대, 최소 힙(heap) 정렬 구현

힙(heap) 자료구조

- 부모가 되는 노드의 값이 자식 노드보다 크거나 작은 자료구조

- 완전이진트리의 구조를 가짐

- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

- 방식에 따라 최대 힙(max heap)과 최소 힙(min heap)으로 나뉨

 

힙(heap)의 구현

- 힙을 저장하는 표준적인 자료구조는 배열 이다.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
    · 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
- 힙에서의 부모 노드와 자식 노드의 관계
    · 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
    · 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
    · 부모의 인덱스 = (자식의 인덱스) / 2

 

힙(heap)의 삽입

- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
- 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

힙(heap)의 삭제

- 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
     ·  최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
- 힙을 재구성한다.

 

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

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다. // 삽입 함수
void insert_max_heap(HeapType* h, element item)
{
	int i;
	// 변수 i는 값을 추가할 위치
	i = ++(h->heap_size);
	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	// i값이 루트라면 반복 진행 안함
	// 추가할 값 > 부모노드의 값
	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 변수는 삭제할 루트 노드
	item = h->heap[1];
	// temp 변수는 힙의 가장 마지막 값, 힙 크기를 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;
		// 한 단계 아래로 이동
		// 반복이 종료되지 않았다면, // parent 위치의 값보다 child 위치의 값이 더 크므로
		// child를 parent 위치로 이동
		h->heap[parent] = h->heap[child];
		// parent 는 child 위치로 이동
		parent = child;
		// 이동된 위치에서 좌측 자식 노드를 감시 대상으로 정함
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

// ---------------------------------------------------------------- 

void insert_min_heap(HeapType* h, element item)
{
	int i;
	// 변수 i는 값을 추가할 위치
	i = ++(h->heap_size);
	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	// i값이 루트라면 반복 진행 안함
	// 추가할 값 < 부모노드의 값
	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_min_heap(HeapType* h)
{
	int parent, child;
	element item, temp;
	// item 변수는 삭제할 루트 노드
	item = h->heap[1];
	// temp 변수는 힙의 가장 마지막 값, 힙 크기를 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;
		// 한 단계 아래로 이동
		// 반복이 종료되지 않았다면, // parent 위치의 값보다 child 위치의 값이 더 크므로
		// child를 parent 위치로 이동
		h->heap[parent] = h->heap[child];
		// parent 는 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_min_heap(h, a[i]);
	}
	for (i = 0; i < n; i++) {
		a[i] = delete_min_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;
}

- 위 소스코드에서 최대,최소 힙 삽입함수와 삭제함수를 구현하였음

- 위 소스코드는 heap_sort 함수에서 최소 힙 함수 2개를 이용하여
   23, 56, 11, 9, 56, 99, 27, 34의 숫자를 오름차순으로 구현하였음

 

 

- 결과창