[자료구조] - 우선순위 큐 /최대 히프/최소 히프/히프 정렬/응용

우선순위 큐 : 우선 순위의 개념을 큐에 도입한 자료구조

우선순위 큐의 응용

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산

우선순위 큐의 구현 방법

• 배열을 사용하는 방법
  정렬이 안된 배열 :
  삽입 : 배열의 맨 끝에 새로운 요소를 추가 -> O(1)
  삭제 : 처음부터 끝까지 모든 요소들을 스캔 -> O(n)

  정렬이 되어 있는 배열:
  삽입 : 탐색 후 삽입 위치 뒤에 있는 요소들을 이동 -> O(n)
  삭제 : 숫자 높은 것이 우선 순위 높다고 가정 맨 뒤에 위치한 요소 삭제 -> O(1)

• 연결 리스트를 사용하는 방법
  배열과 동일한 시간 복잡도
  

• 히프를 사용하는 방법
  삽입 O(log2n)
  삭제 O(log2n)

히프 : 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조

즉 key(부모 노드) >= key(자식 노드) OR key(부모 노드) <= key(자식 노드)

히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다.

히프의 목적 : 삭제 연산이 수행될 때마다 가장 큰(작은) 값을 찾아내기만 하면 됨. 따라서 전체를 정렬할 필요가 없다.

히프의 종류

최대 히프 : 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
최소 히프 : 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리

배열을 이용하여 히프를 저장

부모와 자식의 인덱스 사이에는 다음과 같은 공식이 성립된다.

• 노드 i의 부모 노드 인덱스 = i/2
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

히프의 구현

히프의 정의

히프의 각 요소들을 구조체 element로 정의, element의 1차원 배열을 만들어 히프를 구현한다.

#define MAX_ELEMENT 200
typedef struct {
	int key;
 } element;
 typedef struct {
 	element heap[MAX_ELEMENT];
    int heap_size;	// 현재 히프 안에 저장된 요소의 개수
 } HeapType;

히프의 삽입 연산

일단 새로운 노드를 히프의 마지막 노드로 삽입한 후 부모 노드들과 비교해서 교환해주면 된다.

//현재 요소의 개수가 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;	// 새로운 노드를 삽입
}

마지막 노드에 삽입되고 트리의 높이만큼 부모 노드와 비교하여 교환해야 하므로 O(log2n)이다.

히프의 삭제 연산

최대 히프에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. 빈 루트 노드 자리에는 히프의 마지막 노드를 가져오고 자식 노드와 비교하면서 교환한다.

//삭제 함수
element delete_max_heap(HeapType* h)
{
	int parent, child;
    element item, temp;
    
    item = h->heap[i];
    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[chile + 1].key)
          chiled++;
        if(temp.key >= h->heap[child].key) break;
        
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
   }
   h->heap[parent] = temp;
   return item;
}

디버깅을 하면서 삭제 함수의 프로그램 내부 데이터의 이동을 확인해보니깐 루트를 pop하고, 큰 노드를 찾아서 루트(부모 노드)로 올라간 다음 다 올렸으면 빈 자리에 마지막 노드를 삽입하는 형식이다. 마치 마지막 노드를 위에서부터 떨어뜨려 맞는 자리에 넣는 것처럼 결과가 된다.

마지막 노드를 가져와서 트리의 높이만큼 자식 노드와 비교하여 교환해야하므로 O(log2n)이다.

전체 코드

#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;
// 최대 히프 트리 알고리즘

// 생성 함수
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;
}

히프 정렬

데이터들을 최대 히프로 생성하고 한 번에 하나씩 요소를 히프에서 꺼내서 배열을 뒤쪽부터 저장하면 오름차순으로 정렬하게 된다.

그렇다면 최소 히프로 생성하면 내림차순으로 되것네...

#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;


// 생성 함수
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;
}

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);
}

#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;
}

히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 log2n만큼 소요되고 요소의 개수가 n개이므로 O(nlog2n)이다.

전체 자료를 정렬하는것이 아니라 가장 큰 값 몇개만 필요할 때 히프정렬이 유용함.

히프의 응용

머쉰 스케줄링

최적의 해를 찾는 것은 상당히 어렵지만 근사의 해를 찾는 방법이 있다.
그 중 한가지는 LPT(longest pro-cessing time first)방법이다.
LPT는가장 긴 작업을 우선적으로 기계에 할당하는 것이다. 여기서는 최소 히프를 사용한다. 3개의 기계에 작업 시간이 0으로 초기화 되어있고 각 기계에 작업을 할당하는데 작업 시간이 적은 기계를 선택하고 선택된 기계에 작업 시간을 추가하여 다시 우선 순위 큐에 삽입한다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_ELEMENT 200

typedef struct {
	int id;
	int avail;
} 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,4,3,2,1}; //작업이 정렬되어 있다고 가정
    element m = {0,0};
    HeapType*h;
    h = create();
    init(h);
    
    //avail : 기계 작업 시간, id : 기계 이름
    for(int i = 0; i < MACHINES; i++) {
		m.id = i+1;
        m.avail = 0;
        insert_min_heap(h,m); // 기계 이름과, 작동시간 0으로 초기화
    }

	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);	//작동시간 증가시킨 후 다시 최소히프에 넣는다. 
      }
      for (int i = 0; i < MACHINES; i++) {
		printf("기계 %d번 최종 작업 시간 : %d\n",i+1, h->heap[i + 1].avail);
	  }
      
      return 0;
 }