[자료구조] 우선순위 큐와 힙 - 02 . 힙 구현

[힙 구현]

[Heap.h]

#ifndef Heap_H
#define Heap_H

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

typedef int ElementType;

typedef struct tagHeapNode
{
	ElementType Data;
}HeapNode;

typedef struct tagHeap
{
	//노드 배열
	HeapNode* Nodes;
	//최대용량
	int Capacity;
	//사용중인 사이즈
	int UsedSize;
}Heap;

//힙의 생성
Heap* Heap_Create(int Initialize);
//힙의 삭제
void Heap_Destroy(Heap* heap);
//삽입
void Heap_Insert(Heap* heap, ElementType NewData);
//최소 노드의 삭제
void Heap_DeleteMin(Heap* heap, HeapNode* Root);
//부모 찾기
int Heap_GetParent(int Index);
//왼쪽 자식 찾기
int Heap_GetLeftChild(int Index);
//노드 교환
void Heap_SwapNodes(Heap* heap, int Index1, int Index2);
//노드 출력
void Heap_PrintNodes(Heap* heap);

#endif // !Heap

[Heap.cpp]

#include "Heap.h"

//힙의 생성
Heap* Heap_Create(int Initialize)
{
	Heap* NewHeap = (Heap*)malloc(sizeof(Heap));
	NewHeap->Capacity = Initialize;
	NewHeap->UsedSize = 0;
	NewHeap->Nodes = (HeapNode*)malloc(sizeof(HeapNode) * Initialize);

	printf("size : %d\n",sizeof(HeapNode));
	return NewHeap;
}
//힙의 삭제
void Heap_Destroy(Heap* heap)
{
	free(heap->Nodes);
	free(heap);
}
//삽입
void Heap_Insert(Heap* heap, ElementType NewData)
{
	//삽입할 위치
	int CurrentPositoin = heap->UsedSize;
	//부모의 위치
	int ParentPosition = Heap_GetParent(CurrentPositoin);

	//용량이 가득 찼다면 두배로 재할당
	if (CurrentPositoin == heap->Capacity)
	{
		heap->Capacity *= 2;
		heap->Nodes = (HeapNode*)realloc(heap->Nodes, sizeof(HeapNode) * heap->Capacity);
	}

	//잎 노드 최 우측에 데이터를 넣어준다
	heap->Nodes[CurrentPositoin].Data = NewData;

	//후처리
	//힙 순서 속성 (부모는 자식보다 작다)를 만족할때까지 부모와 교환을 진행한다 .
	while (CurrentPositoin > 0 && heap->Nodes[CurrentPositoin].Data < heap->Nodes[ParentPosition].Data)
	{
		//부모와 자식을 변경
		Heap_SwapNodes(heap, CurrentPositoin, ParentPosition);
		//현재 위치 - 부모 위치를 업데이트
		CurrentPositoin = ParentPosition;
		ParentPosition = Heap_GetParent(CurrentPositoin);
	}
	//삽입한 크기를 반영한다
	heap->UsedSize++;

}
//최소 노드의 삭제
void Heap_DeleteMin(Heap* heap, HeapNode* Root)
{
	int ParentPosition = 0;
	int LeftPosition = 0;
	int RightPosition = 0;

	//Root에 루트노드의 값을 옮긴다
	memcpy(Root, &heap->Nodes[0], sizeof(HeapNode));
	//루트노드를 0으로 만든다
	memset( &heap->Nodes[0],0, sizeof(HeapNode));

	//힙이 사용중인 크기를 줄여준다
	heap->UsedSize--;
	Heap_SwapNodes(heap, 0, heap->UsedSize);
	//좌,우 자식을 찾는다 (비교를 위해)
	LeftPosition = Heap_GetLeftChild(0);
	RightPosition = LeftPosition + 1;

	//힙 순서 속성을 만족할때까지 부모와 자식을 교환한다
	while(1)
	{
		#pragma region 자식중 교환 대상 선정
		//선택된 자식(좌우 자식중 더 작은 자식교)
		int SelectedChld = 0;
		//왼쪽 자식이 없다면 (잎노드인 경우 현재 위치가 올바른 자리이기에 멈춘다)
		if (LeftPosition >= heap->UsedSize)
		break;

		//왼쪽 자식은 있다면 왼쪽 자식을 선택한다
		if (RightPosition >= heap->UsedSize)
		{
			SelectedChld = LeftPosition;
		}
		else//둘다 있다면 두 자식간 비교를 진행한다
		{
			SelectedChld = (heap->Nodes[LeftPosition].Data < heap->Nodes[RightPosition].Data)
			? LeftPosition : RightPosition;
		}
		#pragma endregion

		#pragma region 교환

		//부모가 자식보다 크다면 교환
		if (heap->Nodes[SelectedChld].Data < heap->Nodes[ParentPosition].Data)
		{
			Heap_SwapNodes(heap,ParentPosition,SelectedChld);
			ParentPosition = SelectedChld;
		}
		else//힙 순서 속성을 만족하므로 교환을 멈춘다 (부모보다 자식이 작다)
			break;

		//자식의 위치 변경하여 다시 검사 진행
		LeftPosition = Heap_GetLeftChild(ParentPosition);
		RightPosition = LeftPosition + 1;
		#pragma endregion

	}

	//크기가 가용용량의 반보다 작다면 대할당
	if (heap->UsedSize < heap->Capacity / 2)
	{
		heap->Capacity /= 2;
		heap->Nodes = (HeapNode*)realloc(heap->Nodes, sizeof(HeapNode) * heap->Capacity);
	}
}
//부모 찾기
int Heap_GetParent(int Index)
{
	//현재인덱스 -1 한 값을 2로 나눈 몫은 부모의 위치이다 .
	return (int)((Index - 1) / 2);
}
//왼쪽 자식 찾기
int Heap_GetLeftChild(int Index)
{
	return (Index * 2) + 1;
}
//노드 교환
void Heap_SwapNodes(Heap* heap, int Index1, int Index2)
{
	int CopySize = sizeof(HeapNode);
	HeapNode* Temp = (HeapNode*)malloc(CopySize);

	//인덱스1의 값을 임시노드에 옮긴다
	memcpy(Temp, &heap->Nodes[Index1], CopySize);
	//인덱스2의 값을 인덱스1에 옮긴다
	memcpy(&heap->Nodes[Index1], &heap->Nodes[Index2], CopySize);
	//임시노드의 값을 인덱스2에 옮긴다
	memcpy(&heap->Nodes[Index2], Temp, CopySize);
	free(Temp);
}
//노드 출력
void Heap_PrintNodes(Heap* heap)
{
	int i = 0;
	for (int i = 0; i < heap->UsedSize; i++)
	{
		printf("%d\t", heap->Nodes[i].Data);
	}printf("\n");
}

[HeapTest.cpp]

#include"Heap.h"

int main(void)
{
	Heap* heap = Heap_Create(3);
	HeapNode MinNode;

	Heap_Insert(heap, 12);
	Heap_Insert(heap, 87);
	Heap_Insert(heap, 111);
	Heap_Insert(heap, 34);
	Heap_Insert(heap, 16);
	Heap_Insert(heap, 75);

	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	Heap_DeleteMin(heap, &MinNode);
	Heap_PrintNodes(heap);

	return 0;
}

결과는 다음과 같다