힙(Heap)

각 노드에 저장되어 있는 값이 자식 노드에 저장되어 있는 값보다 크거나 같은 완전 이진 트리 (최대 힙)
각 노드에 저장되어 있는 값이 자식 노드에 저장되어 있는 값보다 작거나 같은 완전 이진 트리 (최소 힙)

연산 알고리즘
– 삽입
– 최댓값 삭제
– 힙 정렬
– 힙 정렬 (공간복잡도를 최소화)
– heapify (완전 이진트리를 힙으로 만드는 연산)

시간복잡도

삽입: O(logn) – 모든 노드와 SWAP한 경우 (최악), O(1) – SWAP 하지 않음 (최선)
최댓값 삭제: O(logn) – 루트부터 한 레벨 씩 내려가면서 SWAP하기 때문
정렬: O(nlogn) – 최댓값 삭제를 n번해서 배열에 거꾸로 저장하기 때문
heapify: O(n) – 리프가 아닌 모든 노드로부터 리프까지 거리의 합만큼 SWAP을 진행할 수 있다. 이 때 거리의 합은 O(n)

힙은 ‘삽입 후 최댓값 삭제’를 가장 효율적으로 할 수 있는 자료구조이다!
시간 복잡도: O(logn), 힙 사용하지 않을 시 최소 O(n)

최대 힙의 삽입,삭제,정렬 소스 (Insertion, Max_delete, Sorting)

#include <stdio.h>
#define MAX_ELEMENT 200
#define size 8

typedef struct {
	int key;
}element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size; // 힙 사이즈가 n이면 heap배열의 원소들이 (idx 1 ~ idx n) 까지 존재 
}HeapType;
typedef HeapType* HeapType_ptr;

// 생성 함수
HeapType_ptr create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

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

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_max_heap(HeapType_ptr h, element item) {
	int i;
	i = ++(h->heap_size);

	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	// 배열로 트리를 구현하니까 부모 노드의 idx는 1 
	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_ptr h) {
	int parent, child;
	element item, temp;

	item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item변수로 옮긴다.
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값을 temp변수로 옮기고 힙 사이즈를 1 줄인다. (처음에는 루트에 위치해있다고 생각) 
	parent = 1;
	child = 2; // 루트의 왼쪽 자식부터 비교한다. 

	// 자식이 힙을 벗어나지 않았으면 반복문 진행 
	while (child <= h->heap_size) {
		// 두 자식노드가 있으면 더 큰 자식노드를 찾는다.
		if ((h->heap[parent * 2].key >= 0) && (h->heap[(parent * 2) + 1].key >= 0)) {
			if ((h->heap[parent * 2].key) > (h->heap[(parent * 2) + 1].key))
				child = parent * 2;
			else
				child = (parent * 2) + 1;
		}
		// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 값이 크거나 같으면 힙 조정할 필요가 X
		if (temp.key >= h->heap[child].key)
			break;
		// 부모 노드 자리에 자식 노드의 키 값을 저장 
		h->heap[parent] = h->heap[child];
		// 한 단계 아래로 이동
		parent = child;
		child *= 2;
	}
	// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 자식 값이랑 크거나 같음 -> 실제로 부모 노드에 저장 
	// (Or) child>h->heap_size로, 위치해야 될 노드에 저장 
	h->heap[parent] = temp;
	return item;
}

// 힙 정렬
void heap_sort(element a[], int n) {
	int i;
	HeapType_ptr 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);
}

int main(void) {
	element list[size] = { 23,56,11,9,56,99,27,34 };

	HeapType_ptr heap = create(); // 힙 생성
	init(heap); // 초기화 

	// 삽입
	for (int i = 0; i < size; i++)
		insert_max_heap(heap, list[i]);

	// 삭제
	printf("힙 삭제: ");
	for (int i = 0; i < size; i++)
		printf("%d ", (delete_max_heap(heap)).key);
	printf("\n");

	// 힙을 이용해서 정렬된 리스트 만들기 
	printf("힙 정렬: ");
	heap_sort(list, size);
	for (int i = 0; i < size; i++)
		printf("%d ", list[i].key);
	printf("\n");

	return 0;
}

Heapify로 최대 힙 만들기 소스

#include <stdio.h>
#include <time.h>
#define MAX_ELEMENT 100
#define size 99

typedef struct {
	int key;
}element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size; // 힙 사이즈가 n이면 heap배열의 원소들이 (idx 1 ~ idx n) 까지 존재 
}HeapType;
typedef HeapType* HeapType_ptr;

// 생성 함수
HeapType_ptr create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

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

// 리스트로 힙 만들기 
void heapify(HeapType_ptr h, element* a) {
	// 리스트 a를 '완전 이진 트리 배열'로 생각한 뒤 h에 일단 저장 
	h->heap_size = size;
	for (int i = 1; i <= h->heap_size; i++)
		h->heap[i] = a[i];
	// -> 힙 성질을 만족하지 않는 h가 생성됨 

	// 힙 성질을 만족하게 할 첫 번째 서브트리 지정 
	int parent, child, parent_save, child_save;
	child = child_save = h->heap_size; // 말단 노드부터 비교 시작 
	parent = parent_save = h->heap_size / 2;

	// 모든 서브트리에 대해 힙 성질 만족 시키기 
	element temp;
	while (parent > 0) {
		// 현재 부모 노드의 값을 temp로 지정 
		temp = h->heap[parent];
		// 자식이 힙을 벗어나지 않았으면 반복문 진행 
		while (child <= h->heap_size) {
			// 두 자식노드가 있으면 더 큰 자식노드를 찾는다.
			if ((h->heap[parent * 2].key >= 0) && (h->heap[(parent * 2) + 1].key >= 0)) {
				if ((h->heap[parent * 2].key) > (h->heap[(parent * 2) + 1].key))
					child = parent * 2;
				else
					child = (parent * 2) + 1;
			}
			// temp 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때,  값이 크거나 같으면 힙 조정할 필요가 X
			if (temp.key >= h->heap[child].key)
				break;
			// 부모 노드 자리에 자식 노드의 키 값을 저장 
			h->heap[parent] = h->heap[child];
			// 한 단계 아래로 이동
			parent = child;
			child *= 2;
		}
		// child>h->heap_size로 말단 노드에 저장 
		h->heap[parent] = temp;
		// 서브트리 재지정 
		parent = parent_save = parent_save - 1;
		child = child_save = parent * 2; // p가 1이고 c가2면 전체 노드를 다 보게 됨 
	}
}

// 삭제 함수 
element delete_max_heap(HeapType_ptr h) {
	int parent, child;
	element item, temp;

	item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item변수로 옮긴다.
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값을 temp변수로 옮기고 힙 사이즈를 1 줄인다. (temp값이 처음에는 루트에 위치해있다고 생각) 
	parent = 1;
	child = 2; // 루트의 왼쪽 자식부터 비교한다. 

	// 자식이 힙을 벗어나지 않았으면 반복문 진행 
	while (child <= h->heap_size) {
		// 두 자식노드가 있으면 더 큰 자식노드를 찾는다.
		if ((h->heap[parent * 2].key >= 0) && (h->heap[(parent * 2) + 1].key >= 0)) {
			if ((h->heap[parent * 2].key) > (h->heap[(parent * 2) + 1].key))
				child = parent * 2;
			else
				child = (parent * 2) + 1;
		}
		// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 값이 크거나 같으면 힙 조정할 필요가 X
		if (temp.key >= h->heap[child].key)
			break;
		// 부모 노드 자리에 자식 노드의 키 값을 저장 
		h->heap[parent] = h->heap[child];
		// 한 단계 아래로 이동
		parent = child;
		child *= 2;
	}
	// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 자식 값이랑 크거나 같음 -> 실제로 부모 노드에 저장 
	// (Or) child>h->heap_size로, 위치해야 될 노드에 저장 
	h->heap[parent] = temp;
	return item;
}

int main(void) {
	// 랜덤값 size개 이용해서 리스트 생성 <인덱스 1부터 size까지 저장> 
	element* list = (element*)malloc(sizeof(element) * (size + 1));
	for (int i = 1; i <= size; i++)
		list[i].key = rand() % 100;

	HeapType_ptr heap = create(); // 힙 생성
	init(heap); // 초기화 

	// 힙 제작 [시간복잡도: O(n)]
	heapify(heap, list);

	// 삭제
	printf("힙 삭제: [ Original Size:%d ]", heap->heap_size);
	for (int i = 1; i <= size; i++)
		printf("\n%d) %d, size:%d", i, (delete_max_heap(heap)).key, heap->heap_size);
	printf("\n");

	free(heap);
}