[자료구조] 우선순위 큐 응용 : 힙 정렬(heap sort), 머신 스케줄링(Machine Scheduling)

우선순위 큐에 대하여 배워보았으니 이제 우선순위 큐를 어디에 사용하고 어떻게 응용하는 지에 대하여 알아보겠습니다. 

 

힙 정렬(heap sort)

힙 정렬(heap sort)은 히프를 사용하는 정렬 알고리즘입니다.

먼저 정렬할 요소들을 최대 히프에 삽입하고 히프에서 하나씩 요소를 삭제하여 저장하면 정렬이 되는 방식입니다.

힙 정렬이 가장 유용한 경우는 가장 큰 값이 몇 개만 필요한 경우입니다.

 

힙 정렬 알고리즘

void heap_sort(element a[], int n)
{
	int i;
	HeapType* h;

	h = create(); // 히프 생성
	init(h); 
	for (i = 0; i < n; i++) {
		insert_max_heap(h, a[i]); // 최대 히프로 삽입
	}
	for (i = (n - 1); i >= 0; i--) {
		a[i] = delete_max_heap(h); // 최대 히프에서 삭제한 값을 오름차순으로 저장
	}
	free(h);
}

int main(void)
{
	element list[8] = { 23, 56, 11, 9, 56, 99, 27, 34 };
	heap_sort(list, 8);
	for (int i = 0; i < 8; i++) {
		printf("%d ", list[i].key);
	}
	printf("\n");
	return 0;
}
// 9 11 23 27 34 56 56 99

최대 히프에서의 삽입과 삭제 연산은 아래 포스팅에 자세히 설명되어 있으니 참고하시기 바랍니다.

[자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제

 

 

 

머신 스케줄링 (Machine Scheduling)

만약 어떤 작업을 처리하는 기계가 m개 존재하고 처리할 작업이 n개 존재한다고 합시다. 이 m개의 기계들로 최소의 시간안에 작업들을 모두 끝내야만 합니다. 이 문제에 대해 최적의 해를 구하는 것은 매우 어렵지만 근사 해는 우선순위 큐를 활용하여 쉽게 찾을 수 있습니다.

 

그러한 방법 중 하나가 가장 긴 작업을 우선적으로 기계에 할당하는 LPT(Longest Processing Time first)방식입니다.

 

LPT(Longest Processing Time first)

맨 위의 표 J1 ~ J7은 각 작업의 기계 사용 시간입니다.

최소 히프는 모든 기계의 종료시간을 저장하고 있습니다. 작업 전 초기에는 모든 기계의 종료시간이 0이며, 히프에서 최소 종료시간을 가지는 기계를 삭제하여 작업을 할당합니다. 그리고 선택된 기계의 종료시간을 업데이트하여 다시 히프에 저장합니다.

 

#define JOBS 7
#define MACHINES 3
int main(void)
{
	int jobs[JOBS] = { 8, 7, 6, 5, 3, 2, 1 }; // 작업은 정렬되어 있다고 가정
	element m = { 0, 0 }; // m.id , m.avail
	HeapType* h;
	h = create();
	init(h);
	// avail 값은 기계가 사용 가능하게 되는 시간
	for (int i = 0; i < MACHINES; i++) {
		m.id = i + 1;
		m.avail = 0;
		insert_min_heap(h, m);
	}
	for (int i = 0; i < JOBS; i++) {
		m = delete_min_heap(h);
		printf("JOB %d을 시간=%d부터 시간=%d까지 기계 %d번에 할당합니다.\n",
			i, m.avail, m.avail + jobs[i] - 1, m.id);
		m.avail += jobs[i];
		insert_min_heap(h, m);
	}
	return 0;
}
/*
JOB 0을 시간=0부터 시간=7까지 기계 1번에 할당합니다.
JOB 1을 시간=0부터 시간=6까지 기계 2번에 할당합니다.
JOB 2을 시간=0부터 시간=5까지 기계 3번에 할당합니다.
JOB 3을 시간=6부터 시간=10까지 기계 3번에 할당합니다.
JOB 4을 시간=7부터 시간=9까지 기계 2번에 할당합니다.
JOB 5을 시간=8부터 시간=9까지 기계 1번에 할당합니다.
JOB 6을 시간=10부터 시간=10까지 기계 2번에 할당합니다.
*/

최소 히프에서 기계를 꺼내서 작업을 할당하고 사용가능 시간을 증가 시킨 후에 다시 최소 히프에 추가합니다.