Hyokyun Yim bio photo

Hyokyun Yim

Koreatech Computer Science Engineering undergraduate 4 grade.

Facebook Github

자료구조 힙을 사용하여 힙소트를 구현.

Overview

Heap 자료구조

  • 힙 이란? 최대값 및 죄소값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조 종류의 하나로 완전 이진트리의 구조를 이루고 있으며 부모 노드와 자식 노드간에 크기를 비교하여 자료를 구성한다.
  • A가 B의 부모 노드이면, A의 키값과 B의 키값 사이에는 대소 관계가 성립한다. 힙에는 두 가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 ‘최대 힙’, 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 ‘최소 힙’이라 부른다. 즉 최대값을 루트에 보내는 힙과 최소값을 루트에 보내는 힙 2종류가 있다.
  • 힙은 연결리스트로도 구현이 가능하지만 그림처럼 배열로도 구현이 가능하다. 최상위 루트A의 키값을 배열 인덱스 1에 넣고 그 아래에 순차적으로 B,C,D … 순서로 넣어준다. (이때 배열0부터 넣어도 상관없으나 구현하기 쉽게 1부터 넣어준다.)
  • 힙의 기능은 특정 값을 삽입하는 기능, 삭제 하는 기능을 가지고 있으며, 정렬을 보장하지 않는다. 삽입 함수의 동작은 새 값이 가장 말단 노드에 삽입이 되었다고 가정했을 경우 siftdown 동작을 실행한다.
  • 즉 삽입된 말단 노드의 부모 노드와 비교하여 삽입한 노드가 더 클 경우 부모 노드의 자리에 넣어버리고 원래 부모 노드에 있던 값은 말단노드로 내린다.
  • 그리고 다시 상단 부모 노드와 비교하여 대소 관계를 비교 후 값을 올릴지 아니면 그대로 둘지 선택한다. 이러한 과정 삽입을 구현한다. 삭제는 가장 최상단 루트 노드의 값을 리턴(삭제) 하고 말단 노드를 루트로 이동시킨 후 다시 siftdown 과정을 수행하여 Heap 구조를 유지한다.

Heap Sort

  • 힙 소트란? 자료구조 힙을 사용하여 데이터를 정렬하는 방식이다. 맨 처음 정렬이 안된 값들을 모두 힙에 저장한 후 힙의 삭제 기능을 실행하여 최상위 루트 값을 Heap이 빌 때까지 모두 뽑아내어 다시 배열에 저장하는 방법으로 정렬을 한다.
  • 최대 값을 루트에 저장하는 힙의 경우 삭제함수를 호출하는데 이때 최상위 루트에 있는 값이 뽑아져 리턴 되고, 다시 이 자리는 말단 노드의 값이 들어간다.
  • 그리고 힙이 삭제되어 하나 줄어들었으므로 힙 구조체의 heapsize를 하나 줄여준다. 그리고 다시 siftdown을 하여 heap을 조정해준다.
  • 이 과정을 반복하여 heapsize가 0이 될 때까지 리턴 값을 받아 배열의 뒤쪽부터 저장시키면 오름차순으로 정렬이 된다.

힙 소트 구현 코드



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

#pragma warning(disable:4996)

//heap 구조체
struct heap
{
	int heapsize;
	int *arr; 
};

void siftdown(heap& H, int i)
{
	// parentIDX:부모노드의 인덱스, largerchildIDX:2개의 자식노드중 큰 자식 노드
	// siftkey 
	int parentIDX, largerchildIDX;  
	int siftkey;
	bool stop;

	siftkey = H.arr[i];
	parentIDX = i;
	stop= false;

	// 높이 h 인 완전 이진 트리라면 높이 h-1의 부모노드 부터 비교를 시작한다.
	// 2 * parentIDX <= H.heapsize 는 비교를 하는 노드가 최대 힙 사이즈를 넘지 않도록 조건을 준 것이고
	// stop!=true 는 루트 노드 값이 자식 값보다 크지 않을경우 반복문이 실행되도록 조건을 주었다.
	while (2 * parentIDX <= H.heapsize && stop!= true)
	{
		// 2*parentIDX 인덱스의 배열에 저장된값과 , H.heapsize 인덱스의 배열에 저장된 값이 같을 경우 
		// 위치를 바꿔줄 필요가 없으므로 2 * parentIDX < H.heapsize 이 조건을 넣었고
		// 그리고 자식 노드의 좌측(2 * parentIDX)과 우측(parentIDX * 2 + 1) 을 비교하여 조건에 맞는 노드의 인덱스를
		// largerchildIDX 에 채워 넣는다.
		if (2 * parentIDX < H.heapsize && H.arr[2 * parentIDX] < H.arr[parentIDX * 2 + 1])
			largerchildIDX = 2 * parentIDX + 1;
		else
			largerchildIDX = 2 * parentIDX;

		// 위 과정에서 선택된 자식노드(largerchildIDX)의 값과 부모노드 값(siftkey)을 비교하여
		// 조건이 true이면 자식값을 부모값의 위치에 넣어주고 parentIDX를 largerchildIDX로 변경시켜준다 
		// false라면 루트 노드가 더 크다는 뜻이므로 stop 을 true 로 변경해 주는 동작을 한다.
		if (siftkey < H.arr[largerchildIDX])
		{
			H.arr[parentIDX] = H.arr[largerchildIDX];
			parentIDX = largerchildIDX;
		}
		else
			stop = true;   // 부모노드 값이 자식 값보다 클경우 stop를 true로 지정
	}
	//부모 노드값과 자식노드간에 변경이 이루어졌다고 가정하면 자식 노드의 위치에 부모노드의 값이 저장된다.
	//아니라면 그위치 그대로
	H.arr[parentIDX] = siftkey;

}

//최상위 루트의 값을 뽑아오는 함수
int root(heap& H)
{
	int keyout;	
	keyout = H.arr[1];			   //최상위 루트의 값을 뽑아내기위해 keyout에 저장
	H.arr[1] = H.arr[H.heapsize];  //원래 최상위 루트의 위치에 말단 노드의 값을 저장시킴
	H.heapsize = H.heapsize - 1;   //값을 뽑아내고 사이즈를 하나 줄임
	siftdown(H, 1);			       //현재 최상위에 말단 노드 값이 들어갔으므로 
								   //siftdown 함수를 사용해 다시 힙으로 맞춰줌
	return keyout;

}

//root 함수를 사용하여 삭제기능을 수행하는 함수
//그리고 추가적으로 배열에 뽑아온 값을 배열의 후방부터 저장함. -> 결과적으로 오름차순으로 정렬됨
void removekeys(int n, heap& H, int S[])
{
	int i;
//최상위 루트로부터 받은 값은 큰 값순으로 받아오기떄문에
//배열의 후방부터 채워넣어준다.
	for (int i = n; i >= 1; i--)			

	{
//root 함수로 받은 값을 변수 a에 저장
//받아온 값들을 배열의 후방부터 저장
		int a = root(H);					
		H.arr[i] = a;						
		
	}
}

//임의의 정수 데이터가 저장된 배열 값들을
//힙으로 만들어줌
void makeheap(int n, heap& H)
{
	H.heapsize = n;

	// n/2를 하는 이유는 높이가 h인 트리일 경우 
	// h-1 에 있는 노드를 부모노드로 취급하면 되므로
	// 그래야 하단의 자식노드들을 비교가능  i=h-1 => i * 2 , i*2 +1 자식노드의 위치들
	for (int i = n / 2; i >= 1; i--)  
	{
		siftdown(H, i);
	}

}

// 만들어진 makeheap 함수와 removekeys 함수로 힙정렬 수행
// num : 원소개수, H : 구조체 heap으로 만들어진 변수의 주소값
void heapsort(int num, heap& H)
{
	makeheap(num, H);
	removekeys(num, H, H.arr);
}



int main()
{
	heap HEAP;		//힙 변수 선언
	FILE *fin, *fout;
	int size;
	int idx = 0;
	int temp = 0;
	char fname[50];

	printf("aa");
	printf("파일명을 입력하세요! Heap 정렬 결과는 result.txt 로 저장됩니다. \n( 입력 예 : xxx.txt )");
	scanf("%s", &fname);

	//데이터의 개수를 읽어오기 위해 fopen, idx 변수에 데이터 수를 카운트함
	fin = fopen(fname, "rb");     //파일이름은 입력으로 받기

	if (fin == NULL)
	{
	printf("파일명이 없습니다.\n");
	return -1;
	}

	//파일속에 저장된 데이터의 수를 확인하기위한 반복문  idx에 값 축적
	while (1)
	{
	if (feof(fin) != 0)
	break;
	fscanf(fin, "%d\n", &temp);
	idx++;
	}
	fseek(fin, 0L, SEEK_SET);			//파일 포인터 위치를 처음으로 리셋


	HEAP.heapsize = idx + 1;             // heapsize 에 힙에 저장된 원소 개수를 저장 50000개
	HEAP.arr = new int[HEAP.heapsize];   // 데이터 50000개를 저장할 동적배열 할당.
	idx = 1;                             // 인덱스 1부터 채워나가므로 1로 초기화
	
	//데이터 뽑아서 HEAP.arr 동적배열에 저장 시키기
	while (1)
	{
	if (feof(fin) != 0)
	break;
	fscanf(fin, "%d\n", &temp);
	HEAP.arr[idx] = temp;
	idx++;
	}
	fclose(fin);

	//힙 정렬함수 호출
	heapsort(HEAP.heapsize, HEAP);

	fout = fopen("result.txt", "wb");   //정렬된 데이터 result.txt 파일에 저장하기
	
	for (int i = 1; i < idx; i++)
		fprintf(fout, "%d\n", HEAP.arr[i]);
	printf("정렬이 완료되었습니다 프로젝트 폴더내 result.txt 를 확인하세요 \n");

	return 0;
}

코드 실행 결과