자료구조와 알고리즘은 항상 뗄래야 뗄 수 없는 관계 마냥 서로 붙어있다. 왜일까? 둘은 어떤 관계이고, 어떤 차이점이 있고, 어떤 공통점이 있길래 항상 붙어있는 걸까?
자료구조 = 알고리즘?
하도 둘을 같이 보다보니 이렇게 생각할 수도 있다. 하지만 이것은 아니다.
아주 단순화 시키면, 프로그램 = 자료구조 + 알고리즘
이라고 볼 수 있다.
컴퓨터를 입력과 출력을 해주는 간단한 기계라고 생각해보자. 컴퓨터에 입력한 자료를 잠시 저장해둘 공간이 필요하다.
여기서, 어떻게 저장할지? 면 자료구조이고,
그 저장된 자료를 어떻게 처리할지? 면 알고리즘이다.
정육점 고기를 예시로 들어보자. 정육점에서 고기를 진열할 때 소-돼지-닭 순으로 진열할 수도 있고, 닭 - 돼지 - 소로 진열할 수도 있다. 이런 ‘어떻게 진열할 것인가’, 가 자료구조이고,
왼쪽에서 오른쪽으로 고기를 살펴볼지, 오른쪽에서 왼쪽으로 고기를 살펴볼지, 가장 큰 덩어리의 고기부터 볼 것인지, 가장 작은 덩어리의 고기부터 볼 것인지. '어디서부터 살펴볼 것인가'가 알고리즘이다.
이 둘이 혼동되는 이유는 자료구조를 만들 때 알고리즘이 개입되어야하기 때문이다.
그 여러 자료구조, 알고리즘 중에서 오늘은 힙에 대해 알아보려고 한다.
우선순위 큐
힙은 우선순위 큐를 위하여 만들어진 자료구조이다. 먼저 우선순위 큐에 대해 조금 알아보자면, 우선순위 큐는 우선순위의 개념을 큐에 도입한 것으로, 데이터들이 우선순위를 가지고 있고, 순위가 높은 데이터가 먼저 나가게되는 자료구조이다. 우선순위 큐의 이용 사례로는 운영 체제에서의 작업 스케쥴링, 네트워크 트래픽 제어 등이 있다. 이 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데, 이 중 힙으로 구현하는 것이 가장 효율적이라고 한다.
힙이란?
완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다. 힙은 여러 개의 값들 중에서 최댓값, 또는 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 특징으로는 큰 값이 가장 상위레벨에 있고, 작은 값이 하위 레벨(max heap)에 있거나, 아예 그 반대(min heap)이거나이다.
간단히 말하면 부모 노드의 키 값이 자식노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
여기서 크면 최대힙, 작으면 최소힙이 되는 것이다.
그리고 이진 탐색 트리에서는 중복된 값을 허용하지 않는데, 힙 트리에서는 중복된 값을 허용한다.
힙의 삽입
- 힙에 새로운 요소가 들어왔다.
- 새로운 노드는 힙의 마지막 노드에 이어서 삽입한다.
- 힙의 조건을 만족할 때까지 새로운 노드를 부모 노드들과 교환한다.
힙의 삽입 구현 코드
/* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수
void insert_max_heap(HeapType *h, element item)
{
int i;
i = ++(h->heap_size); // 힙 크기를 하나 증가
/* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
// i가 루트 노트(index: 1)이 아니고, 삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
while((i != 1) && (item.key > h->heap[i/2].key)){
// i번째 노드와 부모 노드를 교환환다.
h->heap[i] = h->heap[i/2];
// 한 레벨 위로 올라단다.
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}
힙의 삭제
- 최대 힙에서 최댓값은 루트 노드이다. 루트 노드를 삭제한다.
- 삭제된 빈 루트 노드에는 힙의 마지막 노드를 가져온다.
- 힙의 조건을 만족할 때까지 힙을 재구성한다.
힙의 삭제 구현 코드
// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h)
{
int parent, child;
element item, temp;
item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당.
temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 루트 노드를 삭제했으니 힙 크기를 하나 감소
parent = 1;
child = 2;
while(child <= h->heap_size)
{
// 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾음. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
child++;
}
// 더 큰 자식 노드보다 마지막 노드가 크면 while문 중지
if( temp.key >= h->heap[child].key ){
break;
}
// 더 큰 자식 노드보다 마지막 노드가 작으면 부모 노드와 더 큰 자식 노드를 교환
h->heap[parent] = h->heap[child];
// 한 단계 아래로 이동
parent = child;
child *= 2;
}
// 마지막 노드를 재구성한 위치에 삽입
h->heap[parent] = temp;
// 최댓값(루트 노드 값)을 반환
return item;
}