힙 정렬(Heap Sort)

우선순위에 따른 정렬이 가능하다.

 

Declaration

#include <stdio.h>

#define MAX_Q_SIZE 101

typedef enum bool{ false, true }bool;
typedef enum eSelectMenu {
	selectPush = 1,
	selectPop,
	selectPeek,
	selectExit
} eSelectMenu;

typedef struct ProcessInfo {		// 프로세스 정보 저장을 위한 구조체
	int pid;
	int remainingJob;
	bool initialize;
}ProcessInfo;

int queueElement = 0;		//	현재 큐에 있는 프로세스 수
ProcessInfo pQueue[MAX_Q_SIZE];		// 우선순위 큐

bool IsNew(int);
bool IsEmpty(void);
bool IsFull(void);

Min Heap

ProcessInfo 구조체를 선언하고 고유한 pid를 remainingJob이 작은 순서대로 정렬

배열 index는 1부터 시작

Max Haep은 부호가 반대로 되면 된다.

 

Push, Pop

void Push(int pid, int job) {		// 큐에 pid와 남은 작업 시간 추가 (Min heap 구현)
	ProcessInfo temp;
	int i;
	if (IsFull()) {		// 큐가 가득 찼을 경우
		printf("Queue is full\n");
		return;
	}
	i = ++queueElement;		// 큐 요소 증가
	while ((i != 1) && (job < pQueue[i / 2].remainingJob)) {		// 현재 추가하려는 element의 작업시간이 parent의 작업시간보다 적을 경우
		pQueue[i] = pQueue[i / 2];		// parent를 child 위치로 한 단계 내림
		i /= 2;		// child를 parent 위치로 한 단계 올림
	}
	temp.pid = pid; temp.remainingJob = job; temp.initialize = true;
	pQueue[i] = temp;	// 위치 결정
}

ProcessInfo Pop(void) {		// 가장 우선순위가 높은 (작업시간이 적게 남은) element 반환
	ProcessInfo temp, returnPi;
	returnPi.initialize = false;
	int parent, child;

	if (IsEmpty()) {		// 큐가 비었을 경우
		printf("Queue is empty\n");
		return returnPi;
	}
	returnPi = pQueue[1];		// 가장 우선순위가 높은 element

	temp = pQueue[queueElement--];		// 가장 마지막 요소
	parent = 1; child = 2;
	while (child <= queueElement) {
		if ((child < queueElement) && (pQueue[child].remainingJob > pQueue[child + 1].remainingJob))
			child++;		// child 요소 중 작은것을 선택 
		if (temp.remainingJob <= pQueue[child].remainingJob) break;		// child의 남은 작업시간보다 작다면 위치 교환 종료
		pQueue[parent] = pQueue[child];		// child를 parent 위치로 한단계 올림
		parent = child;		// 다음 parent, child 요소와 비교
		child *= 2;
	}
	pQueue[parent] = temp;		// parent 위치로 결정
	return returnPi;		// 우선순위가 가장 높은 element 반환
}

 

Method

ProcessInfo Peek(void) {
	ProcessInfo temp;
	temp.initialize = false;

	if (IsEmpty()) {		// 큐가 비었을 경우
		printf("Queue is empty\n");
		return temp;
	}
	return pQueue[1];
}

bool IsNew(int pid) {		// 현재 큐에 존재하는 pid 인지 확인
	int i;
	for (i = 1; i <= queueElement; i++)
		if (pQueue[i].pid == pid) return false;
	return true;
}

bool IsEmpty(void) {		// 현재 큐가 비었는지 확인
	if (queueElement == 0) return true;
	return false;
}

bool IsFull(void) {		// 현재 큐가 가득 찼는지 확인
	if (queueElement + 1 == MAX_Q_SIZE) return true;
	return false;
}

 

Main

int main(void) {
	int select;
	int pid, job;
	ProcessInfo p;

	while (1) {
		printf("1. push / 2. pop / 3. peek / 4. exit\n");
		printf("select: ");
		scanf_s("%d", &select);
		switch (select) {
		case selectPush:
			printf("pid, job: ");
			scanf_s("%d %d", &pid, &job);
			if (IsNew(pid)) {
				Push(pid, job);
			}
			else {
				printf("Already Exist pid\n");
			}
			puts("");
			break;
		case selectPop:
			p = Pop();
			if (p.initialize) {
				printf("Pop data(pid, job): %d, %d\n", p.pid, p.remainingJob);
			}
			puts("");
			break;
		case selectPeek:
			p = Peek();
			if (p.initialize) {
				printf("Peek data(pid, job): %d, %d\n", p.pid, p.remainingJob);
			}
			puts("");
			break;
		case selectExit:
			printf("Exit Program\n");
			return 0;
		default:
			printf("re\n\n");
		}
		while (getchar() != '\n') {}
	}
}

 

실행 결과