[C언어로 쉽게 풀어쓴 자료구조] Chapter 9 - 우선순위 큐

/*
우선순위 큐 : 우선순위의 개념을 큐에 적용한 것
기존의 큐는 삽입 순서에 따라 순서대로 삭제가 일어났다.
즉, 우선순위가 삽입 순서에 국한되었다.
그러나 우선순위 큐는 삽입순서 뿐만 아니라 다양한 요소들을 우선순위로 설정하여 삭제 순서를 정한다.

우선순위 큐 표현 방법
1. 배열을 사용하는 방법
2. 연결리스트를 사용하는 방법
3. 히프를 사용하는 방법
(히프 heap : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리(완전 이진 트리))
*/

 

// 히프 트리 테스트 프로그램

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
	int key;
} element;
typedef struct {
	element heap[MAX_ELEMENT]; // heap은 1차원 배열로 표현
	int heap_size;
} HeapType;


// 생성 함수 (동적 메모리 할당)
HeapType* create()
{
	return (HeapType*)malloc(sizeof(HeapType));
}

// 초기화 함수
void init(HeapType* h)
{
	h->heap_size = 0;
}

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_max_heap(HeapType* h, element item)
{
	int i;
	i = ++(h->heap_size);

	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	// (삽입된 노드가 부모노드 보다 더클경우 교환)
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;     // 새로운 노드를 삽입
}

// 삭제 함수
element delete_max_heap(HeapType* h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1]; // 삭제할 노드(가장 값이 큰 루트노드)
	temp = h->heap[(h->heap_size)--]; // 가장 말단의 노드 선택
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		// 현재 노드의 자식노드 중 더 작은 자식노드를 찾는다.
		if ((child < h->heap_size) &&
			(h->heap[child].key) < h->heap[child + 1].key)
			child++;
		if (temp.key >= h->heap[child].key) break;
		// 한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

int main(void)
{
	element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
	element e4, e5, e6;
	HeapType* heap;

	heap = create(); 	// 히프 생성
	init(heap);	// 초기화

				// 삽입
	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);

	// 삭제
	e4 = delete_max_heap(heap);
	printf("< %d > ", e4.key);
	e5 = delete_max_heap(heap);
	printf("< %d > ", e5.key);
	e6 = delete_max_heap(heap);
	printf("< %d > \n", e6.key);

	free(heap);
	return 0;
}

/* 출력값
< 30 > < 10 > < 5 >
*/

 

 

// 힙 정렬(heap sort)

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
	int key;
} element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

// =================heap code===================
// 생성 함수
HeapType* create()
{
    // 동적 메모리 할당
	return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h)
{
	h->heap_size = 0;
}
// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_max_heap(HeapType* h, element item)
{
	int i;
	i = ++(h->heap_size);

	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}
// 삭제 함수
element delete_max_heap(HeapType* h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		// 현재 노드의 자식노드 중 더 작은 자식노드를 찾는다.
		if ((child < h->heap_size) &&
			(h->heap[child].key) < h->heap[child + 1].key)
			child++;
		if (temp.key >= h->heap[child].key) break;
		// 한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}
// ============================================
// 힙 정렬 (리스트 a, n : 리스트 a의 크기)
void heap_sort(element a[], int n)
{
	int i;
	HeapType* h;

	h = create(); // 힙 생성
	init(h); // 힙 초기화
	// 힙 h에 리스트 a의 요소 추가
	for (i = 0; i<n; i++) {
		insert_max_heap(h, a[i]);
	}
	// 힙에서 삭제된 요소들을 역순으로 리스트 a에 삽입
	for (i = (n - 1); i >= 0; i--) {
		a[i] = delete_max_heap(h);
	}
	// 동적 메모리 해제 (힙)
	free(h);
}

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

/*출력값
9 11 23 27 34 56 56 99
*/

 

 

// 머신 스케줄링(machine schedling) : 동일한 기계 m개로 처리해야 할 일 n개를 최소 시간내에 끝내는 것
// LPT(Longest Processing time first) : 가장 긴 작업을 우선적으로 기계에 할당 하는 방법

#include <stdio.h>
#define MAX_ELEMENT 200

typedef struct {
	int id; // 기계 id (기계들의 이름)
	int avail; // (available : 이용가능한)
} element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

// 생성 함수
HeapType* create()
{
	return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h)
{
	h->heap_size = 0;
}
// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_min_heap(HeapType* h, element item)
{
	int i;
	i = ++(h->heap_size);

	//  트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	while ((i != 1) && (item.avail < h->heap[i / 2].avail)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;     // 새로운 노드를 삽입
}
// 삭제 함수
element delete_min_heap(HeapType* h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		// 현재 노드의 자식노드중 더 작은 자식노드를 찾는다.
		if ((child < h->heap_size) &&
			(h->heap[child].avail) > h->heap[child + 1].avail)
			child++;
		if (temp.avail < h->heap[child].avail) break;
		// 한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}
#define JOBS 7
#define MACHINES 3

int main(void)
{
	int jobs[JOBS] = { 8, 7, 6, 5, 3, 2, 1 };	// 작업은 정렬되어 있다고 가정
	element m = { 0, 0 };
	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번에 할당한다.
*/