히프 정렬

//우선순위 큐인 히프를 이용한 정렬
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);
}

- 히프 정렬의 복잡도

히프트리의 전체 높이가 거의 log_2 n 이므로(완전이진트리이므로) 따라서 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 log_2 n 만큼 소요된다. 요소의 개수가 n개이므로 전체적으로 O(log_2 n) 의 시간이 걸린다. 이 시간 복잡도는 삽입 정렬같은 간단한 정렬 알고리즘이 O(n^2) 걸리는 것에 비하면 좋은 편이다. 또한 히프 정렬이 최대로 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.

 

 

• 머신 스케줄링

이 문제는 알고리즘 분야에서 상당히 유서 깊은 문제로 많은 응용분야를 가지고 있다. 예를 들어서 서버가 여러 개 있어서 서버에 작업을 분배할 때도 사용할 수 있다. 최적의 해를 찾는 것은 상당히 어렵다. 하지만 근사의 해를 찾는 방법이 있다. 그 중 한 가지가 LPT(longest processing time first) 방법이다. LPT 는 가장 긴 작업을 우선적으로 기계에 할당하는 것이다. 예를 들어서 다음과 같은 순서대로 7개의 작업이 예정되어 있고 동일한 기계가 3대가 있다고 하자. 각 작업들은 기계 사용시간에 따라 다음과 같이 미리 정렬되어 있다고 가정한다.(히프 정렬을 사용할 수도 있다)

J1	J2	J3	J4	J5	J6	J7
8	7	6	5	3	2	1

 

 

• LPT 알고리즘의 구현

여기서는 기계의 종료시간이 중요하다. 종료 시간이 최소인 기계가 항상 선택되기 때문이다. 따라서 기계의 종료 시간을 최소 히프에 넣고 최소 히프에서 기계를 꺼내서 그 기계에 작업을 할당하면 된다. 작업을 할당한 후에는 기계의 종료 시간을 작업 시간만큼 증가시킨 후에 다시 최소 히프에 넣는다.

 

#include <stdio.h>
#include <stdlib.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()
{
  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;
}

 

 

열심히