Prim algorithm with heap

Prim algorithm with heap

 

제가 좋아하는 자료구조는 힙(Heap)이라는 것입니다. 힙은 이진트리 중에 특별한 형태를 사용하고 있습니다. 꽉 찬 이진트리를 사용함으로써 배열을 그대로 이진트리로 사용할 수 있습니다.

이중에서 최소힙과 최대힙이 있는데, 루트의 값이 가장 작은 경우를 최소힙, 가장 큰 경우를 최대힙으로 이해하면 됩니다.

힙의 조건은 다음과 같습니다.

1. 힙의 제일 아래층을 제외하고 꽉 차있고, 제일 아래층은 왼쪽부터 꽉 차있다.
2. 힙의 모든 노드는 하나의 값을 가지고 있다.
3. 각 노드의 값은 자식의 값보다 항상 작다. (최소힙)

최대힙의 경우에는 3)항만 다릅니다.

 

꽉 찬 이진트리이기 때문에 배열로 바로 구현할 수 있습니다. 그렇지 않다면 자식들의 링크를 보관해야 하죠.

 

다음의 힙을 배열로 표현한다면 다음과 같습니다.

 

 

최소힙의 경우 루트는 모든 노드들 중에 가장 작은 값이 들어갑니다. 자식들보다 부모의 값은 작아야 하기 때문에, 가장 작은 값이 루트 노드가 아닌 다른 노드에 있다면, 그 노드의 부모의 값은 더 작은 값이어야 하는데, 부모가 없는 유일한 노드인 루트 노드 외에는 가장 작은 값을 가질 수가 없습니다.

일반적으로 힙 자료구조는 힙정렬에서만 배우기 때문에, 힙 자료구조를 보다 적극적으로 사용할 생각을 못 하는 것 같습니다. 게임 프로그램에서 유명한 A* 알고리즘에서도 사실 이 힙을 사용합니다만, A* 알고리즘을 기술할 때 힙에 대한 언급이 별로 많지 않더군요.

 

A* 알고리즘을 이해하기 위해서는 다익스트라(Dijkstra) 알고리즘을 알아야 하고, 그럴려면 최소 신장 트리의 값을 계산하는 프림(Prim) 알고리즘을 알아야 합니다.

 

힙은 데이터의 개수 n일 때, 데이터의 삽입, 삭제의 시간이 \( O( \log n ) \) 을 만족합니다. 사실 간단하게 \( O( \log n ) \) 이라고 표현했지만, 그보다는 더 적은 시간을 소모합니다.

 

간단하게 힙을 이용한 프림 알고리즘을 기술해보았습니다.

 

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

#define	MAXNODES	128

//	Structure of node.
struct MyNode
{
	int nIndex;
	int nHeapIndex;
	double fValue;
	bool bVisited;
};

//	Structure of heap.
struct MyHeap
{
	MyNode *pkNodes[MAXNODES];
	int nNumber;
};

//	Initialize random.
void InitRandom()
{
	srand(time(0));
	rand();
}

//	Return real random value.
double GetRandom()
{
	return (rand() & 0xfff)/(double)0xfff;
}

//	Add a value into heap.
void AddValueIntoHeap(MyHeap *pkHeap, MyNode *pkNode)
{
	int nCurrent = pkHeap->nNumber++;
	
	while( nCurrent > 0 )
	{
		int nParent = (nCurrent-1)/2;
		if( pkNode->fValue >= pkHeap->pkNodes[nParent]->fValue ) break;
		pkHeap->pkNodes[nParent]->nHeapIndex = nCurrent;
		pkHeap->pkNodes[nCurrent] = pkHeap->pkNodes[nParent];
		nCurrent = nParent;
	}
	
	pkNode->nHeapIndex = nCurrent;
	pkHeap->pkNodes[nCurrent] = pkNode;
}

//	Get minimum value node index from heap.
MyNode *GetValueFromHeap(MyHeap *pkHeap)
{
	//	If heap is empty, return NULL.
	if( pkHeap->nNumber == 0 ) return 0;

	MyNode *pkMinNode = pkHeap->pkNodes[0];
	MyNode *pkLastNode = pkHeap->pkNodes[--pkHeap->nNumber];
	int s = 0, l = 1, r = 2, t = l;

	while( l < pkHeap->nNumber )
	{
		if( r < pkHeap->nNumber && pkHeap->pkNodes[l]->fValue > pkHeap->pkNodes[r]->fValue ) t = r;
		if( pkLastNode->fValue <= pkHeap->pkNodes[t]->fValue ) break;
		pkHeap->pkNodes[t]->nHeapIndex = s;
		pkHeap->pkNodes[s] = pkHeap->pkNodes[t];
		l = 2*t + 1, r = 2*t + 2, s = t, t = l;
	}
	pkLastNode->nHeapIndex = s;
	pkHeap->pkNodes[s] = pkLastNode;

	return pkMinNode;
}

//	Notify the node's value is changed as lower value to heap.
void NotifyChangedToHeap(MyHeap *pkHeap, MyNode *pkNode)
{
	int nCurrent = pkNode->nHeapIndex;

	while( nCurrent > 0 )
	{
		int nParent = (nCurrent-1)/2;
		if( pkNode->fValue >= pkHeap->pkNodes[nParent]->fValue ) break;
		pkHeap->pkNodes[nParent]->nHeapIndex = nCurrent;
		pkHeap->pkNodes[nCurrent] = pkHeap->pkNodes[nParent];
		nCurrent = nParent;
	}
	
	pkNode->nHeapIndex = nCurrent;
	pkHeap->pkNodes[nCurrent] = pkNode;
}

//	Prim algorithm.
double Prim(int n)
{
	MyHeap kHeap;
	MyNode kNodes[MAXNODES];
	double fEdges[MAXNODES][MAXNODES];
	int i, j;

	//	Initialize values.
	kHeap.nNumber = 0;
	for( i = 0 ; i < n ; i++ )
	{
		kNodes[i].nIndex = i;
		kNodes[i].fValue = 2.0;
		kNodes[i].bVisited = false;
		fEdges[i][i] = 0.0;
		for( int j = i+1 ; j < n ; j++ )
		{
			double fRandValue = GetRandom();
			fEdges[i][j] = fRandValue;
			fEdges[j][i] = fRandValue;
		}
	}
	kNodes[0].fValue = 0.0;
	for( i = 0 ; i < n ; i++ )
		AddValueIntoHeap(&kHeap, &kNodes[i]);

	double fSpanSum = 0.0;
	while( true )
	{
		MyNode *pkNode = GetValueFromHeap(&kHeap);
		if( pkNode == 0 ) break;

		//	Accumulate span tree sum.
		fSpanSum += pkNode->fValue;

		//	Mark this node as visited.
		pkNode->bVisited = true;

		int nFrom = pkNode->nIndex;
		for( i = 0 ; i < n ; i++ )
		{
			if( kNodes[i].bVisited == false && fEdges[nFrom][i] < kNodes[i].fValue )
			{
				kNodes[i].fValue = fEdges[nFrom][i];
				NotifyChangedToHeap(&kHeap, &kNodes[i]);
			}
		}
	}

	return fSpanSum;
}

//	Main
int main()
{
	int n[5] = { 20, 40, 60, 80, 100 };
	int i, j;

	InitRandom();

	for( i = 0 ; i < 5 ; i++ )
	{
		double fSum = 0.0;
		for( j = 0 ; j < 100000 ; j++ )
			fSum += Prim(n[i]);
		printf("L(%3d) = %.2lf\n", n[i], fSum/100000.0);
	}
}