Security Note

오늘은 힙에 대해 써보려고 한다.

힙은 

이진트리의 일종으로, 다음의 두 가지 속성을 만족하는 것을 말한다.

1. 트리 내 모든 노드의 부모-자식 관계에서 부모 노드의 키값과 자식 노드의 키값이 일정한 대소관계를 가지고 있어야 한다.
2. 완전이진트리로 구성되어야 한다.

각각이 어떤 것을 의미하는지 살펴보자.

먼저 첫번째 속성의 경우, 힙의 두 가지 유형인 최대힙과 최소힙에 대한 설명으로 이해할 수 있다.
최대힙이란 트리 내에서 부모 노드를 제외한 나머지 모든 노드들의 키가 그것의 부모 모드의 키보다 큰 힙을 말한다.
이에 대한 예시는 아래와 같다.

노드처럼 표시된 동그라미 안에 써있는 숫자를 키라고 할 때, 모든 부모 노드의 키가 자식 노드의 키보다 큰 경우이다.
여기서 모든 부모 노드의 키가 자식 노드의 키보다 작을 경우로 바뀌면 최소힙이 되는 것이다.
아래는 위의 최대힙을 최소힙으로 바꿔 본 것이다.

힙의 첫번째 속성은 이렇게 모든 노드의 부모-자식 관계가 최대힙이면 부모가 더 크도록, 최소힙이면 부모가 더 작도록 일정한 대소관계를 이루고 있어야 한다는 의미였다.

힙의 두 번째 속성은 완전이진트리이어야 한다는 것이다.
완전이진트리가 되려면 우선 모든 내부 노드가 자식을 두 개씩 가지고 있어야 한다.
또한 가장 깊은 레벨의 노드들이 왼쪽부터 채워져있어야 한다. 이를 만족하는 트리의 예시는 다음과 같다.

아래는 완전이진트리가 아닌 경우에 대한 예시이다. 첫번째 트리는 모든 내부 노드가 두 개의 자식을 가지지 않은 경우이며, 두번째 트리는 가장 깊은 레벨의 노드들이 왼쪽부터 채워지지 않은 경우이다.

이렇게 힙은 최대힙이나 최소힙 속성을 만족하면서 완전이진트리인 자료구조를 말한다.

또한 힙에는 루트(root) 노드와 마지막 노드를 가리키는 두 개의 접근점이 있는데, 이를 이용하여 힙에 새로운 값을 추가하거나 삭제할 수 있다. 접근점이 어떤 식으로 사용되는지는 구현 과정에서 함께 보기로 하자.

쉬운 이해를 위해 구현에는 정수형 데이터가 들어있는 선형 배열을 사용하였으며, C언어를 사용했다.

1. 초기화

일반적으로 배열의 인덱스는 0부터 시작한다.
그러나 배열로 힙을 만들 때에는 0번 인덱스는 비우고 시작하는 것으로 생각하고 배열의 크기를 잡는 것이 정신건강에 좋다.

이유는, 배열의 시작 인덱스가 1일 경우 현재 노드의 인덱스를 이용하여 다음의 관계를 표현해낼 수 있게 되기 때문이다.

i : 현재 노드
i * 2 : 왼쪽 자식 노드
i * 2 + 1 : 오른쪽 자식 노드
floor(i / 2) : 부모 노드

따라서 n 개의 데이터를 입력받고자 한다면 배열의 크기는 n+1개가 되도록 하고 데이터는 1번 인덱스부터 넣도록 하자.

2. 힙 생성(삽입)

힙을 생성하는 방식은 두 가지가 있다. 삽입식과 상향식이 여기에 해당되는데, 이들은 데이터를 입력받는 방식에 따른 분류이다.

입력 데이터가 하나씩 들어오는 상황이라면 삽입식 힙 생성을 사용할 수 있고,
입력 데이터가 한 번에 들어오는 상황이라면 삽입식 힙 생성 또는 상향식 힙 생성을 사용할 수 있다.

먼저 삽입식 힙 생성은 입력되는 데이터에 대해 하나씩 삽입 작업을 해주는 것과 같다.

데이터 삽입 절차는 다음과 같다.

1. last가 가리키고 있는 곳을 새로운 노드가 추가될 곳으로 옮긴다.
2. last에 새로 입력받은 데이터를 넣는다.
3. 힙의 순서를 복구한다.

(last : 마지막 노드를 가리키고 있는 접근점, 마지막 노드: 레벨 순회로 데이터를 접근했을 때 제일 마지막에 접근하게 되는 노드)

배열로 구현할 경우 1번과 2번에 대해서는 어려울게 없다.
1번은 last가 가리키고 있는 인덱스값을 하나 증가시켜주면 되고, 2번은  증가된 위치에 데이터를 넣어주면 된다.

문제는 3번이 되는데, 앞에서 힙의 노드 간에는 순서가 존재한다고 언급했다.
그런데 임의의 데이터를 마지막 노드로 추가하게 될 경우 이것에 의해 힙 순서 속성에 위배되는 트리가 만들어질 수 있기 때문에 힙 순서 속성을 유지하기 위한 작업을 해야만 한다. 그림을 보면서 따라가보자.

우선 힙에 임의의 새로운 노드가 추가된 상황을 생각해보자.

이는 기존의 최소힙에 새로운 데이터 1이 추가된 상황이다.
1이 추가되기 이전까지 last는 6을 가리키고 있었는데 데이터 추가를 위해 레벨 순위 상 다음 위치인 4의 왼쪽 자식 위치를 가리키도록 변경된 것이다. (단계1) 그리고 변경된 last 위치에 1을 넣었다. (단계2)

이 힙은 최소힙이어야하는데 1이 추가됨으로 인해 최소힙의 속성에 위배되어버렸다. 4보다 큰 데이터가 와야할 위치에 1이 저장되어있기 때문이다.

원래의 순서를 가지도록 복구하기 위해 새로 추가된 노드에서 시작하여 1보다 작은 노드가 나올 때까지 부모 노드를 타고 올라가면서 값을 맞바꾼다. 이 때 두 노드가 저장된 메모리 자체를 맞바꾸는 것이 아닌 노드 안의 데이터만을 맞바꾸는 식으로 구현하면 불필요한 수고를 덜 수 있다.

이 과정을 upHeap이라고 한다. upHeap 과정을 코드로 구현하면 다음과 같다.

// 재귀적 방식
void upHeap(int idx){
	if(idx <= 1) return;
    
    if(heap[idx] >= heap[idx/2]) return;
    int tmp = heap[idx];
    heap[idx] = heap[idx/2];
    heap[idx/2] = tmp;
  
    upHeap(idx/2);
}

// 비재귀적 방식
void upHeap(int idx){
	int i = idx, tmp;
	while(i > 1 && heap[i] < heap[i/2]){
        tmp = heap[i];
        heap[i] = heap[i/2];
        heap[i/2] = tmp;
        
        i = i/2;
    }
}

위 3단계의 삽입 절차를 코드로 구현하면 다음과 같다.

// heap : 힙, N : 힙(배열)의 크기

void buildHeap(int key){
	N += 1; // step 1
    heap[N] = key; // step 2
    upHeap(N); // step 3
}

삽입식 힙 생성 방식을 사용할 경우 데이터를 하나씩 입력받을 때마다 이 함수를 호출하면 된다.

다음으로 상향식 힙생성은 입력 데이터가 전부 미리 주어져 있을 때만 사용할 수 있는 방식이다.

설명을 위해 방금 봤던 힙을 다시 가져와보자.

삽입식 힙 생성에서는 매번 새로운 노드가 추가될 때마다 일단 제일 마지막 last 위치에 넣고, 그 자리부터 최대 root 노드까지 계속 따라 올라가면서 값을 맞바꾸는 작업(이하 swap)을 했었다. 이러한 방식을 사용하여 한 번 데이터를 추가할 경우 발생하는 시간복잡도는 다음과 같다. (n: 힙에 존재하는 노드의 갯수)

1. last가 가리키고 있는 곳을 새로운 노드가 추가될 곳으로 옮긴다. => 배열의 경우 O(1)
2. last에 새로 입력받은 데이터를 넣는다. => O(1)
3. 힙의 순서를 복구한다. => O(log n) : 힙의 높이 log n , 최악의 경우 last부터 root까지의 모든 경로에 대해 swap을 해주어야 한다.

Total O(log n)

이 작업을 n 개의 데이터가 추가될 때마다 반복한다고 할 경우 전체 힙 생성에 걸리는 시간은 O(n log n)이 된다.

만약 여기서 미리 모든 입력 데이터가 주어져 있어 상향식 힙 생성을 사용할 수 있다고 할 경우 이에 걸리는 시간은 O(n)이 된다. 이것이 상향식 힙 생성을 사용하는 이유이다. 어떻게 O(n)의 시간안에 힙을 만들 수 있는지 보도록 하겠다.

상향식 힙 생성은 이름 그대로 아래에서부터 윗 방향으로 힙을 만들어나간다. 그림을 보자.

이러한 힙을 만들려고 한다. 이건 이미 힙이다. 그런데 지금은 힙을 "만들어나가는" 과정을 보기 위한 것이니까 이것을 힙이 아닌 일반 트리가 되도록 순서를 뒤바꾸겠다.

상향식 힙 생성 방식은 두 개의 부트리를 엮어 하나의 더 큰 트리를 만들어내는 개념으로부터 시작한다.

그리하여 트리 각각의 내부 노드를 root로 갖는 부트리로 생각하여 높이(h) - 1 깊이에 있는 부트리부터 차례대로 힙으로 만든다.

위의 트리를 부트리로 쪼갠다고 하면 아래와 같을 것이다.

가장 작은 크기의 부트리부터 순차적으로 힙으로 만들고 -> 합치는 과정을 반복하여 최종적인 힙을 완성하게 될 것이며,

힙을 만들기 위해 힙 순서를 복구하는 함수를 downHeap이라고 한다.

downHeap에서는 특정 인덱스의 노드를 그것의 자식 노드들과 비교해나가며 힙 순서를 복구한다.

내부노드를 루트로 갖는 부트리의 힙 순서를 downHeap 과정을 통해 힙으로 만든 상황이다.

합칠 두 부트리가 준비되었으므로 8을 기준으로 하여 다시 한 번 downHeap을 수행한다.
(그림 상으로는 노드 8 과 부트리 3, 부트리 2가 각각 떨어져있는 것처럼 보이는데, 실제로는 그렇지 않다. 배열 내에서 일어나는 작업이며 각 노드의 데이터만 바뀌는 것이다.)

이 작업을 코드로 구현하면 다음과 같다.

void downHeap(int idx){
    if(idx*2 > N) return;
    
    int small = idx*2;
    if(idx*2+1 > N){
    	if(heap[small] > heap[idx*2+1]) small = idx*2+1;
    }
    
    if(heap[small] >= heap[idx]) return;
    int tmp = heap[small];
    heap[small] = heap[idx];
    heap[idx] = tmp;
    
    downHeap(small);
}

최소힙을 만드는 과정이기 때문에 조금이라도 더 작은 키를 가지고 있는 자식을 위로 올리려고 하고 있다. 이를 위해 small이라는 변수를 만들어 더 작은 값을 가지고 있는 자식의 인덱스를 구하도록 했다.

만약 최대힙을 만드는 과정이라면 두 자식 중 조금이라도 더 큰 키를 가지고 있는 자식의 인덱스를 big 변수에 넣어 사용하는 식으로 응용하면 될 것이다.

downHeap을 사용하여 상향식 힙 생성을 하는 전체 코드는 다음과 같다.

// heap : 힙, N : 힙(배열)의 크기

// 재귀적 방식
void buildHeap(int idx){
	// 외부노드일 경우 비교를 끝낸다.
	if(idx*2 > N) return;
    
    buildHeap(idx*2);
    buildHeap(idx*2+1);
    downHeap(idx);
}

// 비재귀적 방식
void buildHeap(){
	for(int i = N/2; i > 1; i--){
    	downHeap(i);
    }
}

이미 데이터가 주어진 경우에 대해 내부노드부터 알아서 다 스캔해나가는 방식이기 때문에 여러번 호출할 필요없이 한 번에 끝난다.

시간 복잡도

힙 생성을 하는 두 가지 방안에 대해 살펴봤다. 각각의 시간복잡도는 아래와 같다.

1. 삽입식 힙 생성 : O(n log n)
2. 상향식 힙 생성 : O(n)

삽입식은 위에서 다루었기 때문에 상향식에 대해서만 설명한다.

상향식 힙 생성의 동작 방식의 경우, downHeap 코드를 잘 살펴봤다면 캐치했겠지만 현재 노드의 키가 자식 노드의 키보다 이미 작아서(최소힙) 힙의 순서를 만족하는 경우 더 이상 진행하지 않고 return 한다.

이것이 자식쪽에서부터 시작해서 root로 올라가는 방식이다. 그러므로 부모 노드의 downHeap 과정이 진행될 때 자식 부트리의 경우 이미 힙으로 순서가 맞춰져있는 상태이므로, 비교되고 있는 노드들의 값의 순서에만 이상이 없다면 더이상 복구를 진행할 것이 없다.

이 과정이 이해가 되지 않는다면 아래와 같이 배열을 그린 뒤에 역방향(최소힙이라면 내림차순, 최대힙이라면 오름차순)으로 정렬된 데이터를 넣고 swap이 이루어질 때마다 하나씩 색칠해가면서 과정을 이해해보자. 이미 색칠이 되어있는 자리는 더이상 색칠할 일이 없거나 혹은 한 번 더 색칠하게 된다고 하더라도 그것이 겹치는 횟수만큼 다른 곳에 접근이 이루어지지 않은 원소가 존재할 것이다.

이번 글에서 다루었던 것은 힙에 대한 기본적인 개념과 구현 뿐이었는데, 힙을 이용하여 구현할 수 있는 다른 자료구조나 알고리즘도 있다.

대표적인 것으로 우선순위큐 ADT와 힙정렬이 있다.

이들에 대해서는 별도의 글에서 다루도록 하겠다.

스택만큼이나 기본적인 자료구조인 큐에 대해 알아보려고 한다.

큐란

가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 형태의 자료구조이다.

이러한 형태를 선입선출(FIFO, First-In First-Out)이라 한다.

큐는 특히 일상생활에서 매우 쉽게 볼 수 있는 형태의 자료구조인데, 가장 쉽게 생각해볼 수 있는 것이 줄을 서는 것이다.

일렬로 줄을 서서 어떤 서비스를 받기 위한 차례를 기다릴 때 제일 먼저 줄을 선 사람이 제일 먼저 서비스를 받는다.

이것이 큐이다.

스택에서와 달리 큐를 구현할 때에는 데이터의 맨 앞과 맨 뒤를 가리키도록 하는 변수가 각각 필요하다.

데이터의 맨 앞에서는 삭제가 일어나고 맨 뒤에서는 삽입이 일어난다.

여기에서 맨 앞을 가리키는 것을 front라 하고 맨 뒤를 가리키는 것을 rear라 한다.

이러한 개념을 가지고 큐를 직접 구현해보면서 동작 방식에 대해 설명하겠다. (구현에는 C언어를 사용하였다.)

쉬운 이해를 위해 선형 배열을 사용하여 구현하려고 한다. (선형 배열을 사용할 경우에 발생하는 문제는 잠시 후에 살펴보려고 한다.)

1. 초기화

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;

우선 크기가 5인 배열을 선언하고 0으로 초기화를 하였다.

그런 뒤, front와 rear의 값을 모두 0으로 초기화하였는데, 이 값은 구현하려고 하는 방식에 따라 달라질 수 있다.

여기서 front에는 삭제가 될 곳을 가리키는 곳을 저장하도록 하였고, rear는 추가가 될 곳을 저장하도록 하였다.

2. 삽입

다음으로, 큐에 데이터를 추가하는 메소드인 enqueue()를 구현해보자.

void enqueue(int *queue, int front, int *rear, int data){
	if(*rear - front + 1 == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear += 1
}

큐에 데이터를 추가할 때에는 front의 값은 변화하지 않으므로 rear만 call by reference 형태로 하였다.

배열을 사용하여 구현하고 있기 때문에 최대 삽입 가능 원소 개수에 제한이 있는 배열의 특성상 가득 찰 경우에 대한 예외 처리를 해주어야 한다.

만약 큐가 가득 찬 상태가 아닐 경우 queue의 rear 위치에 data를 넣고 rear의 값을 하나 증가시킨다.

3. 삭제

이번에는 큐에 있는 데이터를 삭제하는 메소드인 dequeue()를 구현해보자.

int dequeue(int *queue, int *front, int rear){
	int data;
	if(rear == front){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front += 1;
    return data;
}

dequeue를 할 때에는 front에서 작업이 일어나므로 값이 변경될 일이 없는 rear는 call by value로 넘겨받도록 하였다.

또한, 큐에 있는 데이터를 삭제할 때에는 구현방법과 관계없이 큐가 비어있을 때에 대한 예외처리를 꼭 해주어야 한다.

큐가 비어있지 않을 경우에는 큐의 front 에 위치한 값을 저장해둔 뒤에 front의 값을 하나 증가시킨다.

이렇게 선형 배열을 사용하여 큐를 구현하면 구현이 단순하다는 장점은 있지만.. 일회성 큐가 되어버린다.

왜냐하면 지금과 같이 크기가 5인 배열을 이용하여 큐를 만들게 되면

5개의 값을 삽입하고 5개의 값을 삭제할 경우 front와 rear값이 모두 배열의 마지막 인덱스를 가리키게 될 것인데,

이후로는 더 이상 가리킬 수 있는 곳이 없어 데이터를 삽입하거나 삭제할 수 없다.

따라서 이를 해결하기 위해 원형 배열이라는 것을 사용하여 다시 구현해보려고 한다.

원형 배열이란

물리적으로는 선형 배열과 다를 것이 없는 일반 배열이지만,

프로그래밍을 할 때 배열의 인덱스를 나타내는 값을 증가시켜줌과 동시에 그것을 다시 배열의 크기로 나눈 나머지를 인덱스로 이용하는 것이다.

원형 배열을 사용할 경우 배열의 인덱스를 마지막 위치(7)까지 가리키게 된다고 하더라도, 여기에 하나 증가시킨 값인 8을 배열의 크기인 8로 나눠 다시 0번째 인덱스를 가리키는 방식으로 사용할 수 있으므로, 배열이 가득 차지 않는 한 배열의 나머지 공간을 계속해서 사용할 수 있게 된다.

이러한 개념을 이용하여 enqueue와 dequeue를 다시 구현하면 다음과 같다.

#define SIZE 5

int queue[5] = { 0 };
int front = 0, rear = 0;

void enqueue(int *queue, int front, int *rear, int data){
	if((SIZE + rear - front) % SIZE == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
}

int dequeue(int *queue, int *front, int rear){
	int data;
    
    if(front == *rear){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    return data;
}

enqueue와 dequeue에서 각각에 대한 처리를 한 후, front와 rear에 1을 더해주지만 이 때 더해준 값을 배열의 전체 크기로 나눈 나머지 값을 front와 rear의 값으로 사용하기 때문에 배열의 범위를 넘어서게 되더라도 다시 0번 인덱스로 돌아오게 된다.

이렇게 원형 배열을 이용하여 구현하면 단순 선형 배열로 큐를 구현할 때에 발생되는 일회적인 사용에 대한 문제는 해결이 된다.

하지만 원형 배열은 새로운 문제점을 야기한다.

바로, 배열이 비어있는 상태일 때와 가득찬 상태에 대한 구분이 안된다는 것이다.

이렇게 코딩을 한 후 실행하면 배열이 꽉 찼음에도 불구하고 비어있는 배열처럼 인식하여 fullQueueException이 발령되지 않는다.

배열이 비어있는 경우 front와 rear 값이 같아지게 되는데, 배열이 꽉 찼을 때에도 front와 rear값이 같아지기 때문이다.

여기에는 이를 해결하기 위한 두 가지 방법이 있다.

첫 번째는 배열에 저장되어있는 원소의 개수를 저장하는 것이고,

두 번째는 배열의 한 자리를 남겨둔 채로 사용하는 것이다.

첫 번째 방법을 사용하면 배열의 메모리를 모두 사용할 수 있지만, 매번 저장되어있는 원소의 개수를 유지해야 한다는 단점이 있고

두 번째 방법을 사용하면 배열의 메모리 한 칸을 낭비하게 되지만,  원소의 개수를 유지하지 않아도 된다.

둘 중 어느 방법을 사용할지는 개발하는 사람의 몫이다.

각각의 방법을 사용하여 구현한 경우를 남겨두겠다.

- 첫번째: 원소의 개수를 저장하는 방법

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;
int count = 0; // 원소의 갯수를 저장할 변수

void enqueue(int *queue, int front, int *rear, int *count, int data){
	if(*count == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
    *count += 1;
}

int dequeue(int *queue, int *front, int rear, int *count){
	int data;
    
    if(*count == 0){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    *count -= 1;
    return data;
}

- 두번째: 배열의 한 칸을 비우고 사용하는 방법

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;

void enqueue(int *queue, int front, int *rear, int data){
	if((*rear + 1) % SIZE == front){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
}

int dequeue(int *queue, int *front, int rear){
	int data;
    
	if(*front == rear){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    return data;
}

시간 복잡도

배열을 사용하여 큐를 구현한 경우 각 작업의 시간 복잡도는 선형 배열에서와 원형 배열에서 모두 O(1)이 된다.

그 밖에도 배열로 큐를 구현하여 사용하게 될 경우, 배열의 특성상 front와 rear 위치가 아닌 다른 위치의 인덱스에도 곧장 접근이 가능하다. 그러나 큐를 큐답게 쓰기 위해서는 꼭 enqueue와 dequeue 작업을 이용하여 삽입과 삭제 위치를 지키면서 사용해야 한다.

끝으로 연결 리스트를 이용하여 큐를 구현한 코드를 첨부하고 마무리하려고 한다.

연결리스트를 이용하여 큐를 구현한 경우에도 시간 복잡도는 배열에서와 마찬가지로 O(1)이 되고,

배열에서와 달리 메모리의 한계가 존재하지 않으므로 fullQueueException 처리를 할 필요가 없게 된다.

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

typedef struct _node {
	int data;
    struct _node *next;
} NODE;

int *front = NULL, *rear = NULL;

NODE* getnode(int data){
	NODE *node = (NODE*)malloc(sizeof(NODE));
    node->next = NULL;
    return node;
}

void enqueue(int **front, int **rear, int data){
	NODE *node = getnode(data);
    
    if(*rear == NULL) *front = node;
    else (*rear)->next = node;
    *rear = node;
}

int dequeue(int **front, int **rear){
	int data;
    NODE *tmp = NULL;
    
    if(*front == NULL){
    	emptyQueueException();
    }
    
    data = (*front)->data;
    tmp = *front;
    *front = (*front)->next;
    
    if(*front == NULL) *rear = NULL; // 값을 삭제한 뒤 남은 노드가 없는 경우 rear에도 NULL 대입
    
    free(tmp);
    return data;
}