[자료구조] 힙(HEAP) 구현

 

UsefulHeap은 우선순위를 함수포인터로 정의하여 heap 구조를 만든다.

 

따라서 함수포인터를 사용할 것이고 그러므로 데이터+순위 조합의 구조체가 필요가 없다

그냥 데이터만 있으면 된다.

 

함수포인터 복습하느라 개고생했네...

참고로 윤성우 자료구조 책 힙부분에 함수포인터 쓰는데 오류있음 ㅇㅇ

 

---

[UsefulHeap.h]

#ifndef __USEFUL_HEAP_H__
#define __USEFUL_HEAP_H__

#define TRUE 1
#define FALSE 0

#define HEAP_LEN 100

typedef char HData;

// typedef로 함수포인터 선언
typedef int (*PriorityComp)(HData d1, HData d2);

typedef struct _heap {
	PriorityComp comp;
	int numOfData;
	HData heapArr[HEAP_LEN];
}Heap;

void HeapInit(Heap* ph, PriorityComp pc);
int HIsEmpty(Heap* ph);

void HInsert(Heap* ph, HData data);
HData HDelete(Heap* ph);

int GetParentIDX(int idx);
int GetLChildIDX(int idx);
int GetRChildIDX(int idx);
int GetHiPriChildIDX(Heap* ph,int idx);

#endif

 

---

[Basic Functions]

void HeapInit(Heap* ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc;
}

int HIsEmpty(Heap* ph) {
	return ph->numOfData == 0 ? 1 : 0;
}

int GetParentIDX(int idx) { return idx / 2; }
int GetLChildIDX(int idx) { return idx * 2; }
int GetRChildIDX(int idx) { return idx * 2 + 1; }

 

---

[GetPriChildIDX]

int GetHiPriChildIDX(Heap* ph, int idx) {
	// 자식이 없으면
	if (GetLChildIDX(idx) > ph->numOfData) return 0;
	// 마지막 자식이면
	else if (GetLChildIDX(idx) == ph->numOfData) return GetLChildIDX(idx);
	// 자식이 둘이면
	else {
		if ((*ph->comp)(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) > 0) return GetLChildIDX(idx);
		else return GetRChildIDX(idx);
	}
}

 

---

[HInsert]

void HInsert(Heap* ph, HData data) {
	int idx = ph->numOfData + 1;

	while (idx != 1) {
		// data가 부모보다 우선이면 
		if ((*(ph->comp))(data,ph->heapArr[GetParentIDX(idx)]) > 0) {
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else {
			break;
		}
	}
	ph->heapArr[idx] = data;
	ph->numOfData += 1;
}

 

 

heap에 데이터추가 시 맨 마지막 노드로 추가하고

부모와 비교해가며 자기 자리를 찾아주는 방식이다.

 

따라서 INSERT 함수는 아래에서 위로 부모와 자식 비교를 해주면 된다.
따라서 활용할 함수는 GetParentIDX 밖에 없다!

---

[HDelete]

HData HDelete(Heap* ph) {
	HData retdata = ph->heapArr[1];
	HData lastdata = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHiPriChildIDX(ph, parentIdx)) {
		// 자식이 더 우선이면
		if ((*ph->comp)(ph->heapArr[childIdx], lastdata) >= 0) {
			ph->heapArr[parentIdx] = ph->heapArr[childIdx];
			parentIdx = childIdx;
		}
		else {
			break;
		}
	}

	ph->heapArr[parentIdx] = lastdata;
	ph->numOfData--;
	return retdata;
}

 

힙에서 노드를 삭제하는 방식은

맨 위에 있는 rootnode를 제거하고

맨 마지막 단말노드를 rootnode로 불러와

자식과 비교하며 내려가면서 자기 자리를 찾아주는 방식이다.

 

따라서 DELETE 함수는 위에서 아래로

부모와 우선순위가 높은 자식을 비교해야하므로

GetPriChildIDX 를 활용하면 된다.

---

[main]

#include <stdio.h>
#include <stdlib.h>
#include "UsefulHeap.h"

int DataPriorityComp(char ch1, char ch2) {
	return ch2 - ch1;
}

int main() {
	Heap heap;
	HeapInit(&heap, DataPriorityComp);

	HInsert(&heap, 'G');
	HInsert(&heap, 'C');
	HInsert(&heap, 'B');
	HInsert(&heap, 'F');
	HInsert(&heap, 'A');
	HInsert(&heap, 'H');
	HInsert(&heap, 'D');
	HInsert(&heap, 'E');

	for (int i = 1; i <= heap.numOfData; i++) { printf("%c ", heap.heapArr[i]); }
	printf("\n\n");
	while (!HIsEmpty(&heap)) {
		printf("%c\n", HDelete(&heap));
	}
	return 0;
}

 

 

첫번째 줄이 heapArr 에 있는 데이터의 순서

두번째줄부터는 HIsEmpty일때까지 Delete한 결과이다

 

이게 왜 배열 순서랑 HDelete 순서랑 틀리냐고 물어볼 수 있는데

 

이유는 힙은 수직관계만 보장하지 좌우관계를 보장하진 않기 때문이다.

 

힙의 데이터들의 관계는 오로지 "부모-자식" 으로만 판단된다

 

따라서 힙은 똑같은 데이터들이 들어간다 하더라도

입력 순서에 따라 완전히 다른 힙이 나올 수 있다

( 물론 완전이진트리라는 구조는 동일하다. 형태는 같지만 데이터들의 순서가 다를 수 있다는 말이다.)

 

위 heapArr에 있는 데이터 순서를 표현하면

 

                    A

              B           C

         E       F   H      D

    G

 

이런 순서다

 

이게 잘못나온거 같지만 제대로 된거다.

수직 관계만 보면 힙구조가 맞기 때문이다!

 

                    1

              2           3

         5       6   8      4

    9

 

어느 노드에서 시작해봐도 부모로 갈수록

우리가 정의한 우선순위(작을수록 우선순위 높음) 에 따라 작아진다.

 

하지만 왜 HDelete를 하면 ABCDEFGH 이 순서대로 출력될까?

 

왜냐하면 HDelete는 데이터들 중 가장 우선순위가 높은 데이터를 뽑아주기 때문이다.

따라서 우리가 아는 우선순위 순서대로 나오게 되는 것이다.