1. 개요
힙은 완전 이진 트리의 일종으로, 부모 노드일수록 우선순위가 높은 데이터를 두는 자료구조이다. 루트 노드에는 가장 우선순위가 높은 데이터가 들어간다. 정렬의 일종인 힙 정렬(Heap Sort)을 해보기 위해 먼저 힙을 만들어보고, 만든 힙을 이용해 데이터를 정렬해보자.2. 힙(heap)이란?
힙(heap)은 원래 무엇을 쌓아 놓은 더미라는 뜻이다. 자료구조의 일종인 힙도 자료를 쌓는데, 우선순위가 가장 높은 자료가 가장 상위에 위치하게 쌓는다. 만약 데이터가 정수인데 우선순위가 가장 큰 수라면 Max Heap이고, 가장 작은 수라면 Min Heap이라고 부른다. 여기서 힙의 장점이 나오는데, 장점은 나중에 이야기하고 아무튼 힙에서 데이터의 저장, 삭제는 어떻게 이루어질까?1. 데이터의 저장
힙(완전 이진 트리, 자식노드보다 부모노드 우선순위가 높음)이 하나 있다고 하자. 여기에 새 데이터를 저장한다. 일단 마지막 위치(우선순위가 가장 낮은 위치)에 저장한다. 그리고 우선순위에 따른 알맞은 위치를 찾을 때까지 계속 부모 노드와 우선순위를 비교하면서 위치를 바꾼다. 부모 노드보다 우선순위가 더 이상 높지 않다면 거기가 맞는 자리이다.
2. 데이터의 삭제
우선순위가 가장 높은 데이터를 삭제하려면 루트 노드를 삭제해야 한다. 그런데 루트 노드를 삭제하면 여기를 다른 노드로 채워야 한다. 보통 마지막 노드를 루트 노드의 자리로 옮기고 나서, 자식 노드와 비교하며 제 자리를 찾게 계속 위치를 바꾼다. 위치를 바꿀 때 비교해야 하는 대상은 왼쪽/오른쪽 자식노드 두 가지이다. 우선순위가 높은 것을 루트 노드 쪽으로 올려야 하기 때문에 둘 중 우선순위가 높은 것과 위치를 바꾼다.
주의사항
힙을 구현할 때 연결 리스트 말고 배열 기반으로 구현해야 한다. 연결 리스트를 쓰면 힙의 마지막 위치에 새 노드를 추가하는 게 쉽지 않기 떄문이다.
배열 기반으로 트리를 만들려면, 각 노드에 고유번호를 부여하고 그 번호를 데이터가 저장되는 배열의 인덱스로 쓰면 된다. 루트 노드의 번호가 1이라고 하자. 그럼 부모 노드와 자식 노드 번호의 관계는 다음과 같다.
왼쪽 자식노드 = 부모 노드 * 2
오른쪽 자식노드 = 부모 노드 * 2 + 1
부모 노드 = 자식 노드 / 2 (몫)
힙을 구현할 때에는 우선순위를 잘 판별해야 한다. 왼쪽 노드가 우선인지 오른쪽 노드가 우선인지. 아래의 코드 중 GetHighPriChildIndex 함수가 그 일을 한다.
우선순위만 잘 판별하면 저장과 삭제는 쉽다. 저장하고 삭제하는 순서는 다음과 같다.
-저장
1. 우선 힙의 가장 마지막 노드(힙은 완전 이진 트리이므로 완전 이진트리를 만족하게끔 저장해야 한다)에 새 데이터를 저장한다.
2. 새 데이터가 들어간 노드와 그 부모 노드를 비교한다. 부모 노드보다 우선순위가 높다면 비교하는 걸 한 단계 올린다.
3. 부모 노드보다 우선순위가 높지 않다면 거기가 새 데이터의 자리이다. 혹은 모든 부모 노드들보다 우선순위가 높다면 루트 노드에 위치한다.
-삭제 : 루트 노드에 있는 데이터 반환 및 삭제
1. 우선 루트 노드에 있는 데이터를 임시 메모리에 저장하고 루트 노드를 비운다.
2. 마지막 노드를 루트 노드로 올린다.
3. 자식 노드들과 비교하면서 맞는 자리를 찾는다.
3. 힙의 C 코드
이번에도 코드는 <열혈 자료구조>에 있는 걸 가져다가 썼다.헤더파일
#ifndef __HEAP_H__
#define __HEAP_H__
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
typedef char HData;
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 HeapIsEmpty(Heap* ph);
void HInsert(Heap* ph, HData data);
HData HDelete(Heap* ph);
#endif
| cs |
실행파일
#include "Heap.h"
void HeapInit(Heap* ph, PriorityComp pc){
ph->numOfData = 0;
ph->comp = pc;
}
int HeapIsEmpty(Heap* ph){
if(ph->numOfData == 0)
return TRUE;
else
return FALSE;
}
int GetParentIndex(int idx){
return idx/2;
}
int GetLeftChildIndex(int idx){
return idx*2;
}
int GetRightChildIndex(int idx){
return idx*2 + 1;
}
int GetHighPriChildIndex(Heap* ph, int idx){
if(GetLeftChildIndex(idx) > ph->numOfData)//자식 노드가 없다면
return 0;
else if(GetLeftChildIndex(idx) == ph->numOfData)//자식 노드가 왼쪽 자식 노드 하나만 존재하면
return GetLeftChildIndex(idx);
else{//자식 노드가 둘 다 존재하면
if(ph->comp(ph->heapArr[GetLeftChildIndex(idx)],
ph->heapArr[GetRightChildIndex(idx)]) < 0)//오른쪽 자식 노드의 우선순위가 높으면
return GetRightChildIndex(idx);
else//왼쪽 자식 노드 우선순위가 높으면
return GetLeftChildIndex(idx);
}
}
void HInsert(Heap* ph, HData data){
int idx = ph->numOfData+1;
while(idx != 1){
if(ph->comp(data, ph->heapArr[GetParentIndex(idx)]) > 0){//부모 노드보다 우선순위가 높다면
ph->heapArr[idx] = ph->heapArr[GetParentIndex(idx)];
idx = GetParentIndex(idx);
}
else
break;
}
ph->heapArr[idx] = data;
ph->numOfData += 1;
}
HData HDelete(Heap* ph){
HData retData = ph->heapArr[1];
HData lastElem = ph->heapArr[ph->numOfData];
int parentIdx = 1;
int childIdx;
while(childIdx = GetHighPriChildIndex(ph, parentIdx)){
if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)//마지막 노드가 자식 노드보다 더 우선순위가 높거나 같으면 반복문 탈출
break;
//마지막 노드가 자식 노드보다 우선순위가 낮으면
ph->heapArr[parentIdx] = ph->heapArr[childIdx];//비교한 자식 노드를 한 단계 위로 올리고
parentIdx = childIdx;//마지막 노드가 저장될 위치를 한 단계 낮춤
}//parentIdx에 마지막 노드의 위치가 저장됨
ph->heapArr[parentIdx] = lastElem;
ph->numOfData -= 1;
return retData;
}
| cs |
메인파일
#include <stdio.h>
#include "Heap.h"
int DataPriorityComp(char ch1, char ch2){
return ch1-ch2;
}
int main(void){
Heap heap;
HeapInit(&heap, DataPriorityComp);
HInsert(&heap, 'A');
HInsert(&heap, 'B');
HInsert(&heap, 'C');
HInsert(&heap, 'C');
HInsert(&heap, 'D');
HInsert(&heap, 'A');
printf("%c \n", HDelete(&heap));
while(!HeapIsEmpty(&heap))
printf("%c \n", HDelete(&heap));
return 0;
}
| cs |
힙은 우선순위 큐를 구현할 때 쓰이는데, 힙과 우선순위 큐의 일치도가 98%쯤 되는 것 같아서 따로 집어넣지는 않는다. 우선순위 큐는 응급실 같은 자료구조인데, 어떻게 넣든 우선순위 높은 데이터부터 나온다.
4. 힙 정렬
저장 말고 힙의 또 다른 기능은 정렬이다. 힙은 저장할 때 자연스럽게 우선순위가 높은 것부터 상위 노드에 넣기 때문에 저장이 곧 정렬이다. 우선순위를 정하는 함수만 잘 만들어놓으면 알아서 정렬해서 저장한다.힙 정렬의 계산복잡도를 빅-오로 표기하면 O(n*logn)이 된다.
참고
윤성우.(2012).열혈 자료구조.오렌지미디어
댓글 없음:
댓글 쓰기