힙(우선순위 큐) 구현 #2

실행소스:github.com/KJT9109/Data_Structure/tree/master/Heap_ProrityQueue

 

앞서 설계한 구조를 가지고 설계를 해보자

 

우선 힙 구조체 선언은 다음과 같다.

 

Heap Data Structure

 
#define MAXIMUM_SIZE 255
 
typedef char HData;
typedef int HNode;
 
typedef HData (*HPriorityCompare)(HData, HData);
 
typedef struct
{
    int heapNode;
    HPriorityCompare HPriorityFunc;
    HData heapData[MAXIMUM_SIZE];
 
}HeapStruct;
 

HeapStruct의 멤버변수

heapNode : 자료구조의 저장 갯수.

HPriorityFunc: 우선순위를 판단하는 함수.

heapData:Heap Data를 저장할 배열

 

 

HeapRawFunc

 

노드를 구하기 위한 함수

 
 
HNode HReadParentNode(HNode curNode)
{
    return curNode / 2;
}
 
HNode HReadChildLeftNode(HNode curNode)
{
    return curNode * 2;
}
 
HNode HReadChildRightNode(HNode curNode)
{
    return (curNode * 2) + 1;
}
 
HNode HFindNode(HeapStruct useHstr, HData wantData)
{
    HNode findNode = 0;
 
    while (strcmp(&(useHstr.heapData[++findNode]), &wantData))
    {
        return findNode;
    }
 
    return 0;
}
 

 

노드의 데이터를 구하기 위한 함수

 

 
HData HReadData(HeapStruct useHstr, HNode curNode)
{
    return useHstr.heapData[curNode];
}
 
 
HData HReadParentData(HeapStruct useHstr, HNode curNode)
{
    return useHstr.heapData[curNode / 2];
}
 
HData HReadChildLeftData(HeapStruct useHstr, HNode curNode)
{
    return useHstr.heapData[curNode * 2];
}
 
HData HReadChildRightData(HeapStruct useHstr, HNode curNode)
{
    return useHstr.heapData[(curNode * 2) + 1];
}
 

 

 

HeapApplicationFunc

API함수 경우엔 Raw Func 을 사용하여 힙 자료구조의 초기화, 삽입, 삭제를 구현 하였다.

void HeapInit(HeapStruct *useHstr)
{
    useHstr->HPriorityFunc = HPriorityCheck;
    useHstr->heapNode = 0;
    memset(useHstr->heapData, 0, sizeof(useHstr->heapData) / sizeof(int));
}
 
HData HeapCount(HeapStruct useHstr)
{
    return useHstr.heapNode;
}
 
void HeapInsert(HeapStruct *useHstr, HData inData)
{
    HData tmpBuff;
    HNode tmpNode;
    useHstr->heapData[++useHstr->heapNode] = inData;
 
    tmpNode = useHstr->heapNode;
 
    /* 부모노드가 존재하고 부모노드와의 우선순위를 비교 했을 때 부모노드가 우선순위가 낮다면 */
    while (HReadParentNode(tmpNode) != 0
            && useHstr->HPriorityFunc(HReadParentData(*useHstr, tmpNode),
                    HReadData(*useHstr, tmpNode))
                    != HReadParentData(*useHstr, tmpNode))
    {
        /* 부모 노드의 데이터를 임시 버퍼에 저장한다. */
        tmpBuff = HReadParentData(*useHstr, tmpNode);
        /* 부모 노드에 현재 노드의 데이터를 저장한다. */
        useHstr->heapData[HReadParentNode(tmpNode)] =
                useHstr->heapData[tmpNode];
        /* 현재 노드에 부모 노드의 데이터를 저장한다. */
        useHstr->heapData[tmpNode] = tmpBuff;
        /* 현재 노드를 부모노드로 변경한다. */
        tmpNode = HReadParentNode(tmpNode);
    }
 
}
 
int HeapDelete(HeapStruct *useHstr, HData inData)
{
    HNode curNode;
    HNode childNode;
 
    HData tmpBuff;
 
    /* 해당 데이터가 Heap Node에  존재 하는지 찾는다.*/
    if (HFindNode(*useHstr, inData) != 0)
    {
        /* Heap의 마지막 노드(우선순위가 낮은)를 삭제된 노드로 옮긴다 */
        curNode = HFindNode(*useHstr, inData);
        useHstr->heapData[curNode] = useHstr->heapData[useHstr->heapNode];
        /* Heap의 마지막 노드를 삭제한다.*/
        useHstr->heapData[useHstr->heapNode--] = 0;
 
        /* 자식 노드있는지 확인한다.*/
        while (HReadChildLeftNode(curNode) < useHstr->heapNode)
        {
            /* 자식 노드들과 우선순위를 비교 후 낮은 우선순위의 자식 노드를 구한다. */
            if (useHstr->HPriorityFunc(HReadChildLeftData(*useHstr, curNode),
                    HReadChildRightData(*useHstr, curNode))
                    == HReadChildLeftData(*useHstr, curNode))
            {
                childNode = HReadChildLeftNode(curNode);
            }
            else
            {
                childNode = HReadChildRightNode(curNode);
            }
 
            /* 현재노드가 자식노드보다 우선순위가 작다면 */
            if (useHstr->HPriorityFunc(HReadData(*useHstr, curNode),
                    HReadData(*useHstr, childNode))
                    == HReadData(*useHstr, childNode))
            {
                /* 현재 노드와 자식노드를 바꿔준다. */
 
                /* 자식 노드를 저장한다. */
                tmpBuff = HReadData(*useHstr, childNode);
                /* 자식 노드에 현재 노드의 데이터를 저장한다. */
                useHstr->heapData[childNode] = useHstr->heapData[curNode];
                /* 현재 노드에 자식 노드의 데이터를 저장한다. */
                useHstr->heapData[curNode] = tmpBuff;
                /* 현재 노드를 자식노드로 변경한다. */
                curNode = childNode;
 
            }
        }
        /* 정상적으로 종료 */
        return 0;
    }
    else
    {
        /* 데이터가 존재하지 않음 */
        return -1;
    }
 
}
 

동작 방식은 앞선 글에 설명하였으므로 따로 설명하지는 않는다.

 

우선순위를 판단할때 사용한 함수는 다음과 같다.

 

HData HPriorityCheck(HData data_A, HData data_B)
{
	if (data_A <= data_B)
		return data_A;

	else
		return data_B;

}

데이터가 작을수록 우선순위가 높다

 

main에서 실행 시킬 때 문자를 집어넣었으므로(HData는 char로 선언됨) A가 가장 맨 앞 index의 와야한다.

 

Test한 Main화면

 

HeapStruct HeapStructure;

int main(void)
{
	printf("Start Heap Structure\r");
	HeapInit(&HeapStructure);

	HeapInsert(&HeapStructure, 'B');
	HeapInsert(&HeapStructure, 'D');
	HeapInsert(&HeapStructure, 'G');
	HeapInsert(&HeapStructure, 'E');
	HeapInsert(&HeapStructure, 'C');
	HeapInsert(&HeapStructure, 'A');
	HeapInsert(&HeapStructure, 'F');

	HeapDelete(&HeapStructure, 'A');
	HeapDelete(&HeapStructure, 'B');


}

Insert 까지만 실행 했을 때 디버깅화면

 

Delete 실행 후 디버깅 화면