자료구조 - 힙(Heap) with C

힙이란?

자료구조의 종류중 하나로 지난번에 포스팅한 트리의 종류중 완전이진트리입니다. 힙의 특징은 자료를 삽입할때 빠르게 정렬을 한 상태로 삽입이 되어 자료를 빼낼때 아주 빠르게 빼낼 수 있습니다. 검색이진트리의 업글버전이라고 생각합니다. 다익스트라 알고리즘을 할때 우선순위 큐(priority queue)로 많이 이용하죠. 

자료구조 - 트리(Tree) with C

기본적인 구조는 이진노드로 이뤄진 트리입니다.

부모노드를 p라고 하고 자식노드를 c라고 가정하면

• 올림차순일 경우엔 p가 c보다 작습니다. 이 경우엔 루트 노드에 제일 작은 값이 들어가서 최소 힙이라고 해요
• 내림차순일 경우엔 p가 c보다 큽니다. 이 경우엔 루트 노드에 제일 큰 값이 들어가서 최대 힙이라고 해요

 

기본적으로 cpp <queue>의 priority queue는 최대힙입니다.

 

힙의 노드 위치를 표시할때 부모노드가 n이라면 왼쪽 자식노드는 2*n, 오른쪽 자식노드는 2*n+1 으로 표시합니다. 루트의 노드 위치는 1입니다.

 

힙을 이용하면 좋은 점은 가장 크거나 작은 몇개의 값들만 접근할때 좋습니다. 입력 받을때 완전히 정리하는게 아니라 일부 값만 정리하기 때문에

 

저는 올림차순인 최소힙을 만들어 보겠습니다. 보통 다익스트라에선 최소힙을 더 많이 쓰니까는🙄

자료 삽입/출력 과정

• 자료의 삽입

 

1. 자료를 힙의 가장 말단에 추가합니다. 그리고 부모 노드와 비교하여 더 작다면 값을 바꿔줍니다. (최소힙이라서 더 작은 값을 위로 올려줍니다.)

부모노드와 비교

2. 값을 바꿔줬다면 다시 한번 부모 노드와 비교해 주고 작다면 또 값을 바꿔줍니다.

어? 또 작네

3. 계속 비교 후 바꿔줍니다. 

결국 루트까지 먹은 1

 

 

• 자료의 제거(출력/삭제)

 

1. 힙에서 루트의 값을 제거(삭제)해 줍니다. 그리고 루트의 자리에 마지막에 위치한 노드의 값을 가져옵니다.

마지막 노드의 값 3이 루트 값으로 이동

2. 자식 노드와 비교해 줍니다. 비교가 종료되면 끝. 자식들중 더 작은 값을 먼저 본다고 생각하면 됩니다. (최소힙이라서)

4와 2중 2가 더 작으니 3과 비교한 후 바꿔줍시다

3이 더 작으므로 여기서 교환을 중지합니다. 자리를 찾은거죠

함수를 만들어 봅시다

힙의 노드와 힙 구조체

typedef struct {
    Data data;
}Node;

노드에는 data 즉 값만 있으면 됩니다. 노드간의 관계는 Heap의 arr배열에서 알 수 있습니다. Data는 int라고 해볼게요.

 

typedef struct {
	Node **arr; //각 노드의 위치 저장
	int size; //현재 몇개의 요소를 갖고있는지
}Heap;

 

힙을 총괄하는 구조체를 하나 만들어 줍니다. 각 번호의 노드를 위치를 저장하는 배열을 만듭니다.

 

Node와 Heap을 다루는 기본적인 함수들입니다.

Node *allocNode() { //dynamic allocation
	return calloc(1, sizeof(Node));
}

void setNode(Node *t, const int *x) {
	t->data = *x;
} //set Node's attribution

void setHeap(Heap *h) {
	h->size = 0;
	h->arr = (Node**) calloc(100005, sizeof(Node*));
	//10만개면 충분할듯
} //Heap basic setting

그리고 push(삽입) pop(제거) front(접근) 함수를 만들었습니다.

//add data into heap
void push(Heap *h, const int *x) {
	Node *t = allocNode();
	setNode(t, x);
	h->size++;
	if (h->size != 1) 
		h->arr[h->size] = t;
	else //루트도 없을때
		h->arr[1] = t;
	int parent = h->size / 2;
	int child = h->size;
	while (h->arr[parent] != NULL) { //루트면 끝나
		if (h->arr[child]->data > h->arr[parent]->data) //더이상 부모노드보다 커도 끝나
			break;
		else {
			int t = h->arr[parent]->data;
			h->arr[parent]->data = h->arr[child]->data;
			h->arr[child]->data = t;//swap

			child /= 2;
			parent = child / 2;
		}
	}
}

void pop(Heap *h) {
	if (h->size != 1) {
		//맨 뒤의 데이터를 앞으로 가져옴
		h->arr[1]->data = h->arr[h->size]->data;
		free(h->arr[h->size]);
		h->arr[h->size] = NULL;
		h->size--;
		int child = 2;
		while (child <= h->size) {
			if (child < h->size && h->arr[child]->data > h->arr[child + 1]->data)
				child++;
			if (h->arr[child / 2]->data <= h->arr[child]->data) //지금께 더 작으면 중지
				break;
			//그게 아니면 여기로 왔다
			int t = h->arr[child / 2]->data;
			h->arr[child / 2]->data = h->arr[child]->data;
			h->arr[child]->data = t; //swap

			child *= 2;
		}
	}
	else {
		free(h->arr[h->size]);
		h->arr[h->size] = NULL;
		h->size--;
	}
	
}

int front(Heap *h) { //맨 위의 원소 보이기
	return h->arr[1]->data;
}

만들고 보니 억지로 노드를 통해서 만들다 보니까 좀 비효율적인것 같네요 ㅠㅠ 배열로 하면 더 간편할듯

문제 추천

백준 1927 최소 힙 링크 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙

그냥 저대로 쓰면 됩니다. 최대 힙도 크기비교 변형만 하면 됩니다.