우선순위 큐(Priority Queue)와 힙(Heap)

1. 우선순위 큐의 이해

우선순위 큐는 그 이름이 의미하듯이 큐와 관련이 있다.

제목만 봐서는 앞서 구현한 '큐'를 확장하는 수준에서 마무리가 될 것 같지만 '큐'의 구현과 '우선순위 큐'의 구현에는 많은 차이가 있다.

---

기억하고 있겠지만 앞서 공부한 '큐'의 핵심 연산 두 가지는 다음과 같았다.

- enqueue: 큐에 데이터를 삽입하는 행위

- dequeue: 큐에서 데이터를 꺼내는 행위

이와 마찬가지로 '우선순위 큐'의 핵심 연산 두 가지도 다음과 같다.

- enqueue: 우선순위 큐에 데이터를 삽입하는 행위

- dequeue: 우선순위 큐에서 데이터를 꺼내는 행위

반면 연산의 결과에는 차이가 있다.

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다.

"들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다."

때문에 큐를 가리켜 '줄서기'에 비유한다면, 우선순위 큐는 '응급상황'에 비유할 수 있다.

예를 들어서 병원의 응급실을 생각해보자.

저녁과 새벽시간에 응급실을 찾는 환자는 다음과 같이 크게 두 부류로 나눌 수 있을 것이다.

- 응급상황 1: 촌각을 다투는, 생명이 위급한 상황의 환자

- 응급상황 2: 촌각을 다투진 않지만 내일까지 기다리기에는 무리인 환자

여기서 응급상황 1의 환자와 응급상황 2의 환자가 동시에 왔을 때, 응급상황 1의 환자를 치료하는 것은 당연하다.

응급상황 2의 환자가 먼저 왔더라도 응급상황 1의 환자가 새로 들어오면 응급상황 1의 환자를 먼저 치료하게 된다.

즉 우선순위가 높은 환자가 먼저 치료를 받는 것이다.

이렇듯 우선순위 큐에서 중요한 것은 우선순위이다.

"우선순위 큐에 저장되는 데이터들은 모두 우선순위를 지녀야 하나요?"

"그럼 우선순위는 어떻게 결정하나요?"

우선순위를 지녀야 한다기 보다는, 데이터를 근거로 우선순위를 판단할 수 있어야 한다.

물론 우선순위의 판단 근거는 프로그래머가 결정할 일이다.

즉 목적에 맞게 우선순위를 결정하면 된다.

"결국 우선순위의 비교를 위해서는 우선순위 정보가 정수로 표현되어야 하겠네요"

틀린 말은 아니지만 그렇지 않은 경우도 있다.

데이터가 영단어인 경우, 그리고 이 영단어의 사전편찬순서가 우선순위 정보를 판단하는 기준인 경우를 예로 들 수 있다.

물론 사전편찬순서의 비교를 위해서 영단어를 이루는 문자의 아스키 코드 값을 비교하는 측면에서는 이 역시 우선순위 정보가 정수로 표현되었다고 볼 수 있다.

"그럼 정수의 값이 클수록 우선순위가 높은 건가요? 아니면 낮을수록 높은 건가요?"

이것도 결정하기 나름이다!

우선순위가 높은 데이터에 큰 값을 부여하면 값이 클수록 우선순위가 높은 것이 되고, 반대로 우선순위가 높은 데이터에 작은 값을 부여하면 값이 작을수록 우선순위가 높은 것이 된다.

"우선순위가 같은 데이터가 존재할 수 있나요?"

물론이다!

우선순위가 서로 다른 데이터들만 저장이 된다면, 자료구조로서 활용할 수 있는 범위가 매우 제한적이지 않겠는가?

---

우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다.

- 배열을 기반으로 구현하는 방법

- 연결 리스트를 기반으로 구현하는 방법

- 힙(heap)을 이용하는 방법

다음 그림에서 보이는 바와 같이, 배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있다.

참고로 다음 그림에서, 저장된 숫자는 데이터인 동시에 우선순위 정보라고 가정하였다.

숫자 1이 가장 높은 우선순위를 뜻하며, 이보다 값이 커질수록 우선순위는 낮아진다고 가정하였다.

이렇듯 배열과 연결 리스트를 이용해서 우선순위 큐를 쉽게 구현할 수는 있지만, 둘 다 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 마지막 노드에 저장된 데이터까지 우선순위 비교를 진행해야 할 수도 있다.

이는 데이터의 수가 적은 경우 큰 단점이 되지 않을 수 있다.

하지만 데이터의 수가 많아지면, 그래서 배열의 크기나 노드의 수가 커지고 많아지면, 성능을 저하시키는 주원인이 된다.

그래서 우선순위 큐는 단순 배열도 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

---

그럼 힙에 대해서 간단히, 이해하기 쉽게 정의를 내려보겠다.

"힙은 '이진 트리'이되 '완전 이진 트리'이다."

"그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다."

"즉 루트 노드에 저장된 값이 가장 커야 한다."

위에서 말하는 '값'은 말 그대로 '값'이 될 수도 있고, 우선순위 큐에서 말하는 '우선순위'가 될 수도 있다.

그런데 우리는 힙을 기반으로 우선순위 큐를 구현할 계획을 갖고 있으니, 위 문장의 '값'은 '우선순위'가 된다.

그럼 위의 문장에서 말하는 형태의 이진 트리를 그림으로 그려 보이겠다.

위와 같이 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 '최대 힙(max heap)'이라 한다.

반면 다음 그림과 같이 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 '최소 힙(min heap)'이라 한다.

이렇듯 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이니, 이를 기반으로 하면 우선순위 큐를 간단히 구현할 수 있지 않겠는가!

참고로 위의 두 그림에서 보이듯이, 힙은 무엇인가를 쌓아 놓은 더미와 흡사하다 하여 붙여진 이름이다.

영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다.

---

2. 힙의 구현과 우선순위 큐의 완성

힙의 구현은 곧 우선순위 큐의 완성으로 이어진다.

따라서 힙과 우선순위 큐를 동일하게 인식하는 경향이 매우 강하다.

하지만 이는 정확하지 않은 것이니, 우선순위 큐와 힙을 어느 정도는 구분할 수 있으면 좋겠다.

힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이라는 사실을 기억하기 바란다.

---

힙을 구현하고 이를 기반으로 우선순위 큐를 구현하고자 한다.

그런데 힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 한다.

따라서 먼저 데이터의 저장과정을 '최소 힙'을 기준으로 설명하고자 한다.

위 그림의 쓰여있는 숫자를 데이터 겸 우선순위라 하자!

그리고 숫자가 작을수록 우선순위가 높다고 가정하자.

그렇다면 위의 그림은 우선순위 관점에서 힙이 맞다!

완전 이진 트리이면서, 어느 위치에서든 다음 식이 성립하기 때문이다.

"자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선순위"

그럼 위 그림의 상황에서 3을 저장한다고 가정해보자.

물론 저장한 이후에도 트리의 우선순위 관계를 유지시키는 것이 관건이다.

그런데 이것이 생각보다 쉽지 않다.

따라서 먼저 전략을 제시하겠다.

---

"새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장합니다."

"그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔줍니다."

"바뀐 다음에도 계속해서 부모 노드와 비교합니다."

"제대로 된 위치를 찾을 때까지 말이죠."

위의 문장에서 말하는 '마지막 위치'는 노드를 추가한 이후에도 완전 이진 트리가 유지되는, 마지막 레벨의 가장 오른쪽 위치를 뜻한다.

앞으로도 이 위치를 '마지막 위치'로 표현하겠으니 기억해 두기 바란다.

자! 그럼 숫자 3을 추가하기 위한 첫 번째 단계를 보이겠다.

위 그림과 같이, 마지막 위치에 노드를 추가하고 부모 노드와 우선순위를 비교한다.

그 결과 이 둘은 서로 위치가 바뀌어야 한다.

따라서 다음 그림과 같이 두 노드의 위치를 바꾼 다음에, 이어서 다시 부모 노드와의 비교를 진행한다.

이번에도 부모 노드의 우선순위가 낮으니, 다음 그림과 같이 두 노드를 바꾼 다음에, 마지막으로 루트 노드와의 비교를 진행해야 한다.

그런데 이번에는 부모 노드보다 우선순위가 높지 않으니, 이로써 숫자 3은 자신의 위치를 찾은 셈이다.

이제 위 그림의 우선순위를 관찰하자.

이 그림이 숫자 3을 추가한 최종결과인데, 여전히 힙의 조건을 만족하고 있음을 알 수 있다.

이렇듯 데이터의 추가과정은 마지막 위치에 데이터를 두고서 부모 노드와의 비교를 통해 자신의 위치를 찾아가는 매우 단순한 방식이다.

---

이번에는 삽입보다 어려울 것으로 생각되는, 하지만 실제로는 삽입과 비슷한 '삭제의 과정'을 고민할 차례이다.

그런데 그에 앞서 무엇을 삭제할 것인지 생각해보자.

우리는 우선순위 큐의 구현을 위해서 힙을 활용할 계획을 갖고 있다.

그런데 우선순위 큐의 삭제는 '가장 높은 우선순위의 데이터 삭제'를 의미하므로, 우리는 힙을 대상으로 다음 내용을 고민해야 한다.

"힙에서 루트 노드를 어떻게 삭제할 것인가?"

물론 루트 노드를 삭제하는 것은 어렵지 않다.

문제는 삭제 후에도 힙의 구조를 유지해야 한다는데 있다.

즉 우리가 고민해야 할 문제의 본질은 다음과 같다.

"힙에서 루트 노드를 삭제한 다음에 이 부분을 어떻게 채울 것인가?"

그럼 이어서 이 문제의 전통적인 해결책을 설명하겠다.

참고로 아래의 문장에서 말하는 '마지막 노드'는 완전 이진 트리에서 마지막 레벨의 가장 오른쪽에 위치한 노드를 뜻한다.

"마지막 노드를 루트 노드의 자리를 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다."

제자리를 찾아가게 한다는 점에서 삽입과 유사한 방법이라는 느낌이 든다.

그럼 위의 문장에서 말하는 해결책을 따라가보겠다.

일단 첫 번째 단계로 힙의 마지막 노드를 루트 노드의 위치로 이동시킨다.

이어서 노드를 삽입할 때와 유사하게, 비교의 과정을 통해서 8이 제 위치를 찾게끔 한다.

즉 다음 그림에서 보이듯이 두 개의 자식 노드 중 우선순위가 높은 3이 저장된 왼쪽 자식 노드와 8이 저장된 노드를 교환한다.

물론 이 과정에서 오른쪽 자식 노드의 우선순위가 높다면, 오른쪽 자식 노드와 교환해야 한다.

참고로 우선순위가 낮은 자식 노드와 교환하면 안 되는 이유는, 그렇게 했을 경우 힙의 기본 조건이 무너지기 때문이다.

이어서 숫자 8은 자식 노드와 비교를 진행한다.

4와 9 중에서 우선순위가 높은 4와 비교를 진행한다.

그 결과 4가 8보다 우선순위가 높으니 다음 그림과 같이 교환을 진행한다.

위 그림에서 8이 저장된 노드도 자식 노드가 존재하는 관계로 비교를 진행해야 한다.

그러나 우선순위가 8이 높은 관계로 이 상태에서 빈 공간을 채우는 과정은 마무리가 된다.

---

힙에 대한 이론적인 설명이 일단락되었으니 다음 질문에 답을 해보자.

"우선순위 큐의 구현에 있어서 단순배열이나 연결 리스트보다 힙이 더 적합한 이유는 어디에 있는가?"

앞서 언급한, 데이터의 우선순위가 높을수록 데이터를 배열의 앞쪽에 위치시키는 방식으로 구현한 우선순위 큐의 성능은 다음과 같이 정리할 수 있다.

• 배열 기반 데이터 저장의 시간 복잡도: $O\left(n\right)$

• 배열 기반 데이터 삭제의 시간 복잡도: $O\left(1\right)$

우선순위가 낮은 데이터를 배열에 저장하는 경우, 배열에 저장된 모든 데이터와의 우선순위 비교과정을 거쳐야 하므로 데이터 저장의 시간 복잡도는 $O(n)$이 되고, 삭제의 과정에서는 맨 앞에 저장된 데이터를 삭제하면 되기 때문에, 이 경우의 시간 복잡도는 $O(1)$이 된다.

이와 유사하게, 앞서 언급한 연결 리스트 기반의 우선순위 큐의 성능도 다음과 같이 정리할 수 있다.

• 연결 리스트 기반 데이터 저장의 시간 복잡도: $O\left(n\right)$

• 연결 리스트 기반 데이터 삭제의 시간 복잡도: $O\left(1\right)$

우선순위가 높을수록, 데이터를 연결 리스트 앞 부분에 배치하는 방식이므로 배열의 경우와 다를 바가 없다.

하지만 힙의 경우는 어떤가? 삽입이나 삭제의 경우 동반되는 비교연산은 주로 부모 노드와 자식 노드 사이에서 일어난다.

그리고 이것이 의미하는 바는 다음과 같다.

"힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 됩니다."

이는 트리의 높이가 하나 늘어날 때마다 비교연산의 횟수가 하나 증가한다는 뜻이므로, 힙의 성능은 다음과 같이 정리할 수 있다.

• 힙 기반 데이터 저장의 시간 복잡도: $O\left(\log n\right)$

• 힙 기반 데이터 삭제의 시간 복잡도: $O\left(\log n\right)$

힙은 완전 이진 트리이므로, 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가한다.

때문에 데이터의 수가 두 배 늘 때, 비교연산의 횟수는 1회밖에 증가하지 않는다.

바로 이 사실을 근거로 위의 시간 복잡도 성능의 결론을 내릴 수 있다.

좀 더 쉽게 설명하자면, 데이터가 늘 때마다 연산의 횟수가 증가하긴 하므로 상수형 시간 복잡도 형태는 아니지만 그렇다고 데이터가 n만큼 늘 때마다 연산 횟수가 그대로 n만큼 느는 것은 아니므로 $O(1)$과 $O(n)$ 사이에 있는 로그형 시간 복잡도 형태라고 짐작할 수 있는 것이다.

이로써 우선순위 큐의 구현에 있어서 배열보다도, 연결 리스트보다도 힙이 어울리는 이유를 객관적으로 정리하였다.

---

우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났으니, 이제는 힙의 구현방법에 대해서 고민해야 한다.

그런데 힙은 트리이다.

앞서 트리를 구현하는 방법에는 '배열'을 이용하는 방법과 '연결 리스트'를 이용하는 방법이 있음을 설명하였으니, 배열과 연결 리스트 중 하나를 선택해야 한다.

"앞서 연결 리스트를 기반으로 트리를 구현하였으니, 당연히 연결 리스트를 힙의 구현 도구로 선택해야겠죠?"

나름 근거 있는 판단이다.

하지만 우리의 생각과 달리 완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 '힙'은 배열을 기반으로 구현해야 한다.

실제로 힙의 구현은 배열을 기반으로 구현하는 것이 원칙으로 여겨지고 있는데, 그 이유는 다음과 같다.

"연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다."

앞서 트리를 배울 때, 부모 노드와 자식 노드를 연결할 때 함수를 가지고 일일이 연결해 주었던 때가 기억이 날 것이다.

이처럼 새로운 노드를, 이미 구현된 트리에서 루트 노드부터 하나씩 찾아가며 마지막 위치에 연결시키는 것은 매우 복잡한 일이 아닐 수 없다.

하지만 배열 기반의 힙이라면 이는 매우 간단한 문제가 된다.

그래서 힙과 같이, 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우에는 연결 리스트가 아닌 배열을 기반으로 트리를 구현해야 한다.

---

앞 챕터에서 배열을 기반으로 트리를 구성하는 방법을 조금 언급하였다.

그때 언급한 내용을 정리하면 다음과 같다.

"노드에 고유의 번호를 부여한다."

"그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다."

위의 문장에서 말하는 바를 설명하는 그림은 다음과 같다.

앞서 한번 보인 그림이지만, 복습을 위해서 한번 더 보이겠다.

위 그림에서 보이듯이, 구현의 편의를 위해서 인덱스가 0인 위치의 배열 요소는 사용하지 않는다는 사실도 앞서 언급하였다.

자! 그럼 배열을 기반으로 힙을 구현하기 위해서 무엇을 더 알아야 할까?

"왼쪽 그리고 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 그리고 부모 노드의 인덱스 값을 얻는 방법"

자식 노드의 인덱스 값을 얻는 방법은 데이터의 삭제를 위해서, 부모 노드의 인덱스 값을 얻는 방법은 데이터의 추가를 위해서 필요하다.

그럼 이 두 가지 방법을 소개하겠다.

- 왼쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 x 2

- 오른쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 x 2 + 1

- 부모 노드의 인덱스 값: 자식 노드의 인덱스 값 / 2

의외로 간단하다.

이진 트리는 레벨이 증가함에 따라서 추가할 수 있는 자식 노드의 수가 두 배씩 증가하는 구조다 보니, 2를 나누고 곱하는 방식으로 부모 노드와 자식 노드의 인덱스 값을 구할 수 있다.

---

그럼 먼저 힙을 위한 헤더파일을 소개하겠다.

SimpleHeap.h

#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE	1
#define FALSE	0

#define HEAP_LEN	100

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
	Priority pr;	// 값이 작을수록 높은 우선순위
	HData data;
} HeapElem;

typedef struct _heap
{
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;

/*** Heap 관련 연산들 ****/
void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

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

#endif

사실 위의 헤더파일은 순수한 힙의 구현을 위한 헤더파일이 아닌, 우선순위 큐의 구현을 염두에 두고 정의한 헤더파일이다.

그리고 이 사실은 다음 구조체의 정의에서 느낄 수 있다.

typedef struct _heapElem
{
	Priority pr;	// 값이 작을수록 높은 우선순위
	HData data;
} HeapElem;

이는 힙에 저장될 데이터의 모델을 정의한 구조체이다.

그런데 이 구조체는 우선순위 정보를 별도로 담을 수 있도록 정의되어 있다.

이는 우선순위 큐의 구현을 고려했다는 뜻이다.

따라서 위의 헤더파일에 선언된 HDelete 함수는 우선순위 큐와 마찬가지로, 데이터의 삽입 순서에 상관없이 우선순위에 근거하여 삭제가 이뤄지도록 정의할 것이다.

---

이어서 헤더파일에 선언된 함수들의 정의를 보이겠다.

그런데 이를 보기에 앞서 다음 사실들을 정리하고 기억할 필요가 있다.

- 힙은 완전 이진 트리이다.

- 힙의 구현은 배열을 기반으로 하며 인덱스 0인 요소는 비워둔다.

- 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

- 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.

- 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다.

이 중에서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호가 일치한다는 사실을 제외하면 나머지는 앞서 언급한 것들이다.

그럼 이제 아래의 코드를 분석해보자.

SimpleHeap.c

#include "SimpleHeap.h"

void HeapInit(Heap * ph) // 힙의 초기화
{
	ph->numOfData = 0;
}

int HIsEmpty(Heap * ph) // 힙이 비었는지 확인
{
	if(ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

int GetParentIDX(int idx) // 부모 노드의 인덱스 값 반환
{ 
	return idx/2; 
}

int GetLChildIDX(int idx) // 왼쪽 자식 노드의 인덱스 값 반환
{ 
	return idx*2; 
}

int GetRChildIDX(int idx) // 오른쪽 자식 노드의 인덱스 값 반환
{ 
	return GetLChildIDX(idx)+1; 
}

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
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->heapArr[GetLChildIDX(idx)].pr 
						> ph->heapArr[GetRChildIDX(idx)].pr)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

// 힙에 데이터 저장
void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData+1;
	HeapElem nelem = {pr, data}; 

	while(idx != 1)
	{
		if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
			break;
	}
	
	ph->heapArr[idx] = nelem;
	ph->numOfData += 1;
}

// 힙에서 데이터 삭제
HData HDelete(Heap * ph)
{
	HData retData = (ph->heapArr[1]).data;    // 삭제할 데이터 임시 저장
	HeapElem lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;    // 루트 노드의 Index
	int childIdx;

	while(childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		if(lastElem.pr <= ph->heapArr[childIdx].pr)
			break;

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}

	ph->heapArr[parentIdx] = lastElem;
	ph->numOfData -= 1;
	return retData;
}

위의 파일에는 함수들이 다수 정의되어 있는데, 이 중에서 GetHiPriChildIDX 함수의 구현에 대한 설명이 필요할 것 같다.

우선 이 함수의 기능 및 역할을 정리해보겠다.

"함수 GetHiPriChildIDX에 노드의 인덱스 값을 전달하면, 이 노드의 두 자식 노드 중에서 우선 순위가 높은 것의 인덱스 값을 반환한다."

"인자로 전달된 노드에 자식 노드가 없으면 0을 반환하고, 자식 노드가 하나인 경우에는 그 노드의 인덱스 값을 반환한다."

이제 GetHiPriChildIDX 함수가 힙의 구현에 있어서, 어떤 상황에서 호출될지 짐작할 수 있을 것이다.

그럼 이번에는 이 함수를 다시 한번 보이면서 주석을 통한 설명을 진행하겠다.

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->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr)
			return GetRChildIDX(idx); // 오른쪽 자식 노드의 인덱스 값 반환
  
        // 왼쪽 자식 노드의 우선순위가 높다면
		else
			return GetLChildIDX(idx); // 왼쪽 자식 노드의 인덱스 값 반환
	}
}

위의 함수에서는 자식 노드가 하나도 존재하지 않는 상황을 다음의 연산문을 통해서 확인하고 있는데 이 부분이 잘 이해되지 않을 수 있다.

if(GetLChildIDX(idx) > ph->numOfData)   
	return 0;

힙은 완전 이진트리이므로 오른쪽 자식 노드만 존재하는 상황은 발생하지 않는다.

따라서 왼쪽 자식 노드가 없다면 자식 노드가 존재하지 않는 것으로 판단할 수 있다.

그리고 힙은 완전 이진 트리이므로 다음과 같은 특성이 있다.

"자식 노드가 하나도 존재하지 않는 노드는 단말 노드입니다."

그런데 단말 노드의 왼쪽 자식 노드의 인덱스 값은 힙에 저장된 노드의 수를 넘어선다.

단말 노드의 왼쪽 자식 노드는 존재하지 않으니 말이다.

그래서 위의 연산문으로 자식 노드의 유무를 확인할 수 있는 것이다.

그럼 이번에는 자식 노드가 하나만 존재하는 경우를 판단하기 위한 다음 연산문을 보자.

위의 설명을 잘 이해했다면 이 연산문도 이해가 될 것이다.

else if(GetLChildIDX(idx) == ph->numOfData) 
	return GetLChildIDX(idx);

반복되는 말이지만, 힙은 완전 이진 트리이므로 하나뿐인 자식 노드는 다음의 특징을 갖는다.

"하나뿐인 자식 노드는 왼쪽 자식 노드이다."

"그리고 힙의 마지막 노드이다."

따라서 위의 연산문을 통해서 자식 노드가 하나인 상황을 판별할 수 있는 것이다.

그럼 지금 설명한 GetHiPriChildIDX 함수와 관련이 있는 HDelete 함수를 소개하겠다.

HDelete 함수의 구현 부를 보기 이전에, 앞서 그림을 통해 설명한 노드의 삭제과정을 다시 한번 관찰하자.

그리하여 다음 사실을 파악하기 바란다.

"힙의 마지막 노드를 루트 노드의 위치에 올린 다음에, 자식 노드와의 비교과정을 거치면서 아래로 내린다."

"자신의 위치를 찾을 때까지 내린다."

따라서 우리는 다음과 같이 판단할 수 있다.

"루트 노드로 올려진 마지막 노드는 자신의 위치를 찾을 때까지 아래로 이동하면서 자신의 위치를 찾아간다."

"하지만 이러한 빈번한 이동을 코드에 그대로 담을 필요는 없다."

"최종 목적지가 결정되면 마지막 노드만 단번에 그리로 옮기면 된다."

앞서 보인 HDelete 함수는 이러한 생각을 반영하여 구현하였다.

때문에 그림을 통해서 설명한 삭제의 방법과 차이가 있다고 생각할 수 있지만 사실은 같은 것이다.

그럼 이어서 구현의 이해를 돕는 주석을 포함하여 HDelete 함수를 다시 한번 보이겠다.

HData HDelete(Heap * ph)
{
	HData retData = (ph->heapArr[1]).data; // 반환을 위해서 삭제할 데이터 저장
	HeapElem lastElem = ph->heapArr[ph->numOfData]; // 힙의 마지막 노드 저장

    // 아래의 변수 parentIdx에는 마지막 노드가 저장될 위치정보가 담긴다.
	int parentIdx = 1; // 루트 노드가 위치해야 할 인덱스 값 저장
	int childIdx;

    // 루트 노드의 자식 노드 중 우선순위가 높은 노드를 시작으로 반복문 시작
	while(childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		if(lastElem.pr <= ph->heapArr[childIdx].pr) // 마지막 노드와 우선순위 비교
			break; // 마지막 노드의 우선순위가 높으면 반복문 탈출

        // 마지막 노드보다 우선순위 높으니, 비교대상 노드의 위치를 한 레벨 올림
		ph->heapArr[parentIdx] = ph->heapArr[childIdx]; 
		parentIdx = childIdx; // 마지막 노드가 저장될 위치정보를 한 레벨 내림
	}  // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장됨

	ph->heapArr[parentIdx] = lastElem; // 마지막 노드 최종 저장
	ph->numOfData -= 1;
	return retData;
}

위의 함수에서 다음 사실만 파악하면 앞서 그림을 통해 설명한 삭제의 과정과 같은 것임을 알 수 있을 것이다.

"HDelete에서는 마지막 노드가 있어야 할 위치를 parentIdx에 저장된 인덱스 값을 갱신해가며 찾아가고 있다."

HDelete 함수가 호출되면서 변수 parentIdx는 1로 초기화된다.

그런데 1은 루트 노드의 인덱스 값이므로, 변수 parentIdx가 1로 초기화 된 이 상황을 마지막 노드를 루트 노드로 옮긴 상황으로 간주할 수 있다.

그리고 while 반복문의 끝에 위치한 다음 두 문장의 실행은, 루트 노드로 옮겨진 마지막 노드와 우선순위가 높은 자식 노드와의 교환이 이뤄지는 상황으로 간주할 수 있다.

// childIdx에 위치한 노드를 부모 노드의 위치로 올림, 실제로 올린다
ph->heapArr[parentIdx] = ph->heapArr[childIdx]; 

// parentIdx에 위치한 노드를 자식 노드의 위치로 내림, 실제로 내리진 않는다
parentIdx = childIdx;

이렇듯 올릴 땐 실제로 올리고, 내릴 땐 실제로 내리지 않으면서 그 위치 정보만 갱신함으로써 함수를 구현한 것이다.

---

HDelete 함수의 정의를 이해하였는가?

그렇다면 HInsert 함수는 쉽게 이해할 수 있다.

유사한 성격의 함수이기 때문이다.

그럼 앞서 설명한 삽입의 과정을 정리해 보겠다.

"새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장합니다."

"그리고는 우선순위의 비교를 통해서 자신의 위치를 찾을 때까지 위로 올립니다."

HDelete 함수를 구현할 때와 마찬가지로 HInsert 함수를 구현할 때에도, 새로운 데이터가 담긴 노드를 이리저리 이동시킬 필요가 없다.

새로운 노드가 있어야 할 위치의 인덱스 값만 유지를 해도 된다.

그럼 주석을 포함한 함수의 정의를 보이겠다.

void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData+1; // 새 노드가 저장될 인덱스 값을 idx에 저장
	HeapElem nelem = {pr, data}; // 새 노드의 생성 및 초기화

    // 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
	while(idx != 1)
	{
        // 새 노드와 부모 노드의 우선순위 비교
		if(pr < (ph->heapArr[GetParentIDX(idx)].pr)) // 새 노드의 우선순위가 높다면
		{
            // 부모 노드를 한 레벨 내림, 실제로 내림
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];

            // 새 노드를 한 레벨 올림, 실제로 올리지는 않고 인덱스 값만 갱신
			idx = GetParentIDX(idx);
		}
		else // 새 노드의 우선순위가 높지 않다면
			break;
	}
	
	ph->heapArr[idx] = nelem; // 새 노드를 배열에 저장
	ph->numOfData += 1;
}

위의 함수에서도 새로운 노드가 저장되어야 할 위치 정보를 변수 idx를 통해서 계속 갱신해 나가고 있다.

따라서 앞서 그림을 통해서 설명한 노드의 삽입과정을 그대로 코드로 옮긴 것으로 볼 수 있다.

완성된 힙의 테스트를 위한 main 함수와 그 실행결과를 보이겠다.

---

SimpleHeapMain.c

#include <stdio.h>
#include "SimpleHeap.h"

int main(void)
{
	Heap heap;
	HeapInit(&heap); // 힙의 초기화

	HInsert(&heap, 'A', 1); // 문자 'A'를 최고의 우선순위를 저장
	HInsert(&heap, 'B', 2); // 문자 'B'를 두 번째 우선순위를 저장
	HInsert(&heap, 'C', 3); // 문자 'C'를 세 번째 우선순위를 저장
	printf("%c \n", HDelete(&heap)); // A 출력

	HInsert(&heap, 'A', 1); // 문자 'A'를 한 번 더 저장
	HInsert(&heap, 'B', 2); // 문자 'B'를 한 번 더 저장
	HInsert(&heap, 'C', 3); // 문자 'C'를 한 번 더 저장
	printf("%c \n", HDelete(&heap)); // A 출력

	while(!HIsEmpty(&heap))
		printf("%c \n", HDelete(&heap)); // B B C C 출력

	return 0;
}

힙을 완성하였으니 이를 기반으로 우선순위 큐를 구현할 차례이다.

그런데 앞서 말했듯이 우선순위 큐를 고려하여 힙을 구현했기 때문에 우리는 사실상 우선순위 큐를 구현한 것이나 다름없다.

따라서 이번 챕터는 여기서 마치도록 하겠다.