[C/자료구조] 우선순위 큐(Priority Queue)/힙(Heap)

Sujung Shin·2022년 11월 15일
0

자료구조

목록 보기
2/3

1. 우선순위 큐(Priority Queue)란?

  • 우선순위 큐
    들어온 데이터에 우선순위를 부여하여 우선순위가 작은/큰 순서대로 데이터를 삭제하는 추상 데이터 타입

(1) 우선 순위 큐의 다방면 활용

시뮬레이션 게임(사건의 시작을 우선순위로 두고), 네트워크 트레픽 제어, 운영 체제에서의 작업 스케줄링, 수치해석적인 계산 등에 사용된다.
네트워크 패킷 중에서 네트워크 관리와 관련된 패킷들은 다른 패킷보다 우선순위를 가지게 된다. 또한 운영체제에서도 System Process는 Application Process보다 우선순위를 가지게 된다.

(2) 우선 순위 큐 추상자료형

  • 객체 : n개의 element 형의 우선 순위를 가진 요소들의 모임
  • 연산:
    create() ::= 우선순위 큐를 생성한다.
    init(q) ::=우선순위 큐 q를 초기화한다.
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사한다.
    is_full(q) ::= 우선순위 큐 q가 가득 찼는지 검사한다.
    insert(q, x) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
    find(q) ::= 우선 순위가 가장 높은 요소를 반환한다.

2. 힙(Heap)

(1) 힙(Heap)이란?

  • 우선순위 큐를 구현하기 위한 가장 효율적인 구조
  • 완전 이진트리(complete binary tree)의 일종
  • 삽입, 삭제 시 O(logn)O(logn)의 시간 복잡도가 보장이 되어있다.

(2) 힙(Heap)의 개념

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

  • key(부모노드)key(부모노드) >=>= key(자식노드)key(자식노드) 관계가 항상 성립한다.

  • 힙 트리에서는 이진트리와 달리 중복된 값을 허용한다.
    힙 트리의 예

(3) 힙(Heap)의 종류

힙에는 두 가지 종류의 힙 트리가 존재한다. 하나는 부모 노드의 key값이 자식 노드보다 큰 최대 힙(max heap), 또 다른 하나는 부모 노드의 key값이 자식 노드보다 작은 최소 힙(min heap)이 있다.

(4) 힙(Heap)의 개념적 구현


힙은 기본적으로 완전 이진트리이기 때문에 루트 노드에 1부터 왼->오 자식 노드 순서대로 차례대로 배열의 인덱스를 부여하면, 다음과 같은 자료구조에 힙을 저장할 수 있다.

  • 어떤 노드의 왼쪽이나 오른쪽 자식의 인덱스를 알고 싶으면 이 식을 이용하자.

  • 왼쪽 자식 노드의 index = 2*(부모 노드 index)

  • 오른쪽 자식 노드 index = 2*(부모 노드 index)+1

  • 부모 노드 index = 자식 노드 index/2

(4) 힙의 구현

(1) 힙의 정의

힙의 각 요소들을 element로 정의하고, element의 1차원 배열을 만들어 힙을 구현한다. 이때 heap_size는 현재 힙 안에 저장된 요소의 개수이다.

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

위의 정의를 이용하여 힙을 생성할 때는 다음과 같이 한다.

HeapType heap;
HeapType *heap = create(); // 메모리 동적할당 이용

(2) 삽입 연산(Insertion Operation)

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 말단 노드에 삽입한 다음 부모노드들과 차례대로 교환하여 힙의 성질을 만족 시켜주어야 한다.

[최대 힙 트리에서의 삽입 Algorithm]
1. heap_size+1을 해준다.(힙 크기 하나 증가)
2. key값에 따라 알맞게 삽입될 배열의 인덱스 자리 를 찾는다.
2-1. 루트노드가 아니고, 부모 노드의 키 값보다 삽입될 노드의 키 값이 크면
2-2. 부모노드 키 값↔삽입될 노드 키 값(swap)
2-3. 인덱스 값/2(=승진)
3. 증가된 힙 크기의 인덱스 배열 자리에 element를 삽입해준다.

/* 최대 힙에서의 삽입 함수 구현 */
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 = i/2;
  }
  h->heap[i] = item;
}

(3) 삭제 연산(Deletion Operation)

삭제 연산은 회사에서 사장 자리가 비게 되면 먼저 제일 말단 사원을 사장 자리로 올린 다음에 강등시키는 것과 비슷하다.
최대 힙에서의 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다.
최대 힙에서의 최대값은 루트 노드이므로 루트 노드가 삭제된다.
루트 노드의 삭제 후에 힙의 재구성이 중요하게 된다.

[최대 힙 트리에서의 삭제 Algorithm]
1. 루트 노드 값의 반환을 위하여 item변수로 옮긴다.
2. 말단 노드를 루트 노드로 옮긴다.
3. 힙의 사이즈를 하나 줄인다.
4. 재구성
4-1. 루트의 왼쪽 자식부터 비교를 시작한다.
4-2. i가 힙 트리의 크기보다 작으면(힙 트리를 벗어나지 않았다면)
4-3. 오른쪽 자식 vs 왼쪽 자식
4-4. 두 개의 자식 노드 중 큰 값의 인덱스를 largest로 옮긴다.
4-5. largest의 부모 노드가 largest보다 크면
4-5-1. 중지
4-5-2. 그렇지 않으면 largest ↔ largest 부모 노드
4-5-2-1. 한 레벨 밑으로 내려간다.(=강등)
5. 최대값 반환

/* 최대 힙에서의 삽입 함수 구현 */
void delete_max_heap(HeapType *h) {
	int parent, child;
    element item, temp;
    item = 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;
 }

(4) 전체 프로그램 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 200

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

HeapType *create() {
  return (HeapType *)malloc(sizeof(HeapType));
}

void init(HeapType *h) {
  h->heap_size = 0;
}

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() {
  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 > ", e6.key);

  free(heap);
  return 0;
}

::실행 결과::

3. 힙(Heap)의 활용

(1) 힙 정렬

최대 힙을 이용하면 정렬을 할 수 있다.
시간 복잡도 : O(nlogn)O(nlogn)

(2) 머신 스케줄링(LPT Algorithm)

어떤 공장에 동일한 기계가 m개 있다고 하자. 우리는 처리해야 할 작업을 n개 가지고 있다. 각 작업이 필요로 하는 기계의 사용시간은 다르다고 하자. 우리의 목표는 모든 기계를 풀가동하여 가장 최소의 시간 안에 작업들을 끝내는 것이다.
이를 머신 스케줄링 이라고 한다.

(2)-1 LPT 알고리즘

머신 스케줄링 이슈는 근사의 해를 찾는 방법인 LPT(longest processing time first) 알고리즘으로 해결할 수 있다.
LPT 알고리즘은 기본적으로 최소 힙을 이용하며 '가장 긴 작업을 우선적으로 기계에 할당' 하는 것이다.

다음과 같은 순서로 7개의 작업이 미리 예정되어 있고 동일한 기계가 3대가 있다고 가정하자. 각 작업들은 기계 사용 시간에 따라서 다음과 같이 미리 정렬되어 있다.(힙 정렬을 이용하여 구현할 수 있다)

여기서는 최소 힙을 사용한다.

  • 최소 힙은 모든 기계(M1, M2, M3)의 종료 시간을 저장하고 있다.
  • 처음에는 어떤 기계도 사용되지 않으므로 모든 기계의 종료 시간은 0이다.
  • 힙에서 최소 종료시간을 갖는 기계를 삭제하여서 작업을 할당한다.
  • 선택된 기계의 종료 시간을 업데이트하고 작업 J1이 이 기계에 할당된다.
  • 다음 작업은 J2로서 7시간을 차지한다. M2와 M3가 비어있으므로 M2에 할당하자.
  • 다음 작업은 J3로서 6시간을 차지한다. M3가 비어있으므로 M3에 할당하자.
  • 나머지 작업들도 비슷하게 적용된다.

(2)-2 LPT 알고리즘의 구현

#include <stdio.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/2] = h->heap[i];
    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(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;
  }

:: 실행 결과 ::

profile
Sujung Shin
백문이불여일타
이전 포스트

[C++/자료구조] 그래프(Graph)

다음 포스트

(작성 중)[C++/자료구조] 합집합 찾기(Union-Find)

0개의 댓글