우선순위 큐(Priority Queue)

안효빈·2024년 6월 19일

자료구조

목록 보기
10/10

1. 우선순위 큐

우선순위 큐: 데이터들이 우선 순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가게 되는 큐

우선순위 큐는 가장 일반적인 큐이다. 스택과 큐도 우선순위 큐를 이용하여 구현할 수 있기 때문이다.
주로 다음과 같은 분야에서 쓰인다

- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링

우선순위 큐의 ADT는 다음과 같다.

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

우선순위 큐는 0개 이상의 요소의 모임이다. 각 요소들은 우선 순위값을 갖고 있다.
가장 중요한 연산은 삽입과 삭제 연산이다. 최소 우선순위 큐는 낮은 요소를 먼저, 최대 우선순위 큐는 높은 요소를 먼저 삭제한다.

2. 우선순위 큐의 구현 방법

우선순위 큐는 여러 방법으로 구현할 수 있다.
1. 배열을 사용

정렬 O 배열: 삽입 O(n), 삭제 O(1)
정렬 X 배열: 삽입 O(1), 삭제 O(n)
정렬 O 연결리스트: 삽입 O(n), 삭제 O(1)
정렬 X 연결리스트: 삽입 O(1), 삭제 O(n)
히프: 삽입 O(lognlog n), 삭제 O(lognlog n)

3. Heap

heap는 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료 구조다.
간단히 말하면, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리이다. 또한 히프트리는 중복된 값을 허용하지 않는다.

히프의 종류는 다음과 같이 2가지이다.(편의상 최대히프를 사용할 예정)

  • 최대 히프(max heap): 부모 노드의 키값 >= 자식 노드의 키값
  • 최소 히프(min heap): 부모 노드의 키값 <= 자식 노드의 키값

히프는 완전 이진트리이기 때문에 차례대로 번호를 붙일 수 있다. 인덱스 0은 사용되지 않는다.

어떤 노드의 왼쪽이나 오르쪽 자식의 인덱스를 알고 싶으면 다음의 식을 사용하면 된다.

왼쪽 자식의 인덱스 = (부모의 인덱스) 2
오른쪽 자식의 인덱스 = (부모의 인덱스) 2 + 1

부모의 인덱스를 알고 싶으면 다음의 식을 사용하면 된다.

부모의 인덱스 = (자신의 인덱스) / 2

n개의 노드를 갖고 있는 힙의 높이는 O(lognlog n)이다.
마지막 레벨h를 제외하고는 각 레벨 i에 2i−12^{i-1}개의 노드가 존재한다.

4. 히프의 구현

  1. 히프의 정의
    히프는 1차원 배열로 구현이 가능하여, element 구조체로 정의한다. element 안에는 1차원 배열을 정의하고, 현재 히프 안에 저장된 요소의 개수를 나타내는 heap_size 변수를 선언한다.
#define MAZ_ELEMENT 200
typedef struct{
	int key;
}element;
typedef struct{
	element heap[MAZ_ELEMENT];
    int heap_size;
} HeapType;

HeapType heap; //정적 메모리 할당 사용
HeapType *heap = create() //동적 메모리 할당 사용
  1. 삽입 연산
    신입사원을 생각하면 된다. 신입사원은 가장 말단에 위치하지 않는가? 다음과 같은 순서대로 삽입연산을 진행하면 된다.
	1. 번호순으로 가장 마지막 위치에 이어 새로운 요소를 삽입
    2. 부모노드와 비교하여 교환

실제 코드에서 구현은 부모 노드만 끌어내린 후, 삽입될 위치가 확실해지면 새로운 노드를 그 위치로 이동한다.

//현재 요소의 개수가 heap_size인 heap 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; //새로운 노드를 삽입
}
  1. 삭제 연산
    삭제 연산은 사장이 잘리면 신입사원을 사장자리로 올린 후, 능력에 따라 강등시키는 것으로 생각하면 된다.
	1. 루트 노드를 삭제하고, 히프의 마지막 노드를 가져옴
    2. 루트에서 말단노드까지 경로에 있는 노드들을 교환하여 히프의 성질을 만족시킴

//삭제함수
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;
}
  1. 다음은 전체 프로그램이다. 먼저 3개의 요소를 삽입 후, 3개의 요소를 삭제하여 화면에 출력했다. 최대 히프이므로 값이 큰 순서대로 출력됨을 알 수 있다.
#include <stdio.h>
#include <stdlib.h>

#define MAZ_ELEMENT 200
typedef struct{
	int key;
}element;

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

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

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

//현재 요소의 개수가 heap_size인 heap 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;
}

5. 히프의 복잡도 분석

삽입 연산에서 최악의 경우, 루트 노드까지 올라가야 하기 때문에 O(log2nlog_2 n) 걸린다. 삭제 연산도 마찬가지로 아래 레벨까지 내려가야 하므로 O(log2nlog_2 n) 걸린다.

6. 히프 정렬

최대 히프를 이용하여 정렬이 가능하다. 먼저 정렬해야 될 n개의 요소들을 최대 히프에 삽입한다. 삭제되는 요소들은 값이 증가되는 순서이다.(최소히프의 경우)
따라서 하나의 요소를 삽입하거나 삭제할 때 O(log2nlog_2 n)만큼이 소요되고, 전체적으로 O(nlog2nlog_2 n)만큼의 시간이 걸린다.

#include <stdio.h>
#include <stdlib.h>

//앞의 최대히프 코드를 여기에 추가

//우선순위 큐인 히프를 이용한 정렬
void heap_sort(element a[], int n)
{
	int i;
    HeapType* h;
    
    h = create();
    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;
}

7. 머쉰 스케줄링

동일한 기계가 m개, 처리해야 하는 작업이 n개이다. 모든 기계를 풀가동하여 가장 최소의 시간 안에 작업들을 모두 끝내는 것이 목표이다. 최적의 해를 찾는 것은 어렵지만, 근사의 해를 찾는 방법이 존재한다. 바로 LPT이다. 이는 가장 긴 작업을 우선적으로 기계에 할당한다. 따라서 최소 히프를 사용한다.
기계의 종료 시간을 최소 히프에 넣고, 최소 히프에서 기계를 꺼내서 그 기계에 작업을 할당하면 된다. 할당 후, 기계의 종료 시간을 작업 시간만큼 증가시킨 후에 다시 최소히프에 넣는다.

#include <stdio.h>
#include <stdlib.h>

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, 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
안효빈
피넛버터
이전 포스트

이진 탐색 트리

0개의 댓글