[힙 구현]
[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;
}
결과는 다음과 같다
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 해시 테이블 - 01 . 해시와 해시 테이블 (0) | 2023.04.03 |
---|---|
[자료구조] 우선순위 큐와 힙 - 03 . 우선순위 큐 구현 (0) | 2023.04.03 |
[자료구조] 우선순위 큐와 힙 - 01 . 우선순위 큐와 힙 (0) | 2023.03.30 |
[ 자료구조 ] 탐색 - 04 - 3 . 레드 블랙 트리 <구현> (1) | 2023.03.12 |
[ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제> (0) | 2023.03.10 |