09 우선순위 큐 (C언어로 쉽게 풀어쓴 자료구조)

9.1 우선순위 큐 추상 데이터 타입

우선순위 큐의 소개

우선순위 큐의 사용: 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥴링, 수치 해석적인 계산 등

우선순위 큐는 배열, 연결리스트 등 여러 가지 방법으로 구현이 가능한데 우리는 가장 효율적인 히프(heap)로 구현~

 

최소 우선순위 큐: 가장 우선순위가 낮은 요소를 먼저 삭제

최대 우선순위 큐: 가장 우선순위가 높은 요소를 먼저 삭제

 

9.2 우선순위 큐의 구현방법

배열을 사용하는 방법

정렬X배열

삽입 O(1) : 그냥 배열 맨 끝에 요소 추가

삭제 O(n): 가장 우선순위가 높은 요소를 찾아야 한다. 정렬이 안 되어있으므로 처음부터 끝까지 다 스캔해야 한다

 

정렬O배열

삽입 O(n): 삽입위치를 찾고->이동 시켜서 빈자리 만들고->삽입해야함

삭제 O(1) : 숫자가 높은 것이 우선순위가 높다고 가정하면 젤 뒤에 거 삭제하면 됨

 

연결리스트를 사용하는 방법

정렬X연결리스트

삽입 O(1) : 첫 번째 노드로 삽입시키는 것이 유리. 배열과 달리 다른 요소 이동시킬 필요X(just 포인터 변경)

삭제 O(n): 포인터를 따라서 모든 노드를 뒤져보아야 한다

 

정렬O연결리스트

이 경우 우선 순위가 높은 요소가 앞에 위치하는 것이 유리하다. 우선순위 1st가 첫 번째 노드가 되도록 하자~

삽입 O(n): 우선순위값을 기준으로 삽입 위치를 찾아야 한다

삭제 O(1) : 첫 번째 노드를 삭제하면 된다

 

히프를 사용하는 방법

히프(heap): 완전이진트리의 일종으로 우선순위큐를 위하여 특별히 만들어진 자료구조

-느슨한 정렬 상태 유지

 

9.3 히프

히프의 개념

히프(heap): 완전 이진트리 기반의"더미"와 모습이 비슷한 특정 자료구조

-여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어짐

key(부모노드) >= key(자식노드)

-부모 노드의 키값이 자식 노드의 키 값보다 항상 큰 이진트리

-히프트리에서는 중복값을 허용한다(이진탐색트리에서는 허용X)

-히프의 목적: 삭제 연산이 수행될 때 가장 큰 값을 찾아내는 것(가장 큰 값은 루트노드에~)

-히프는 완전이진트리(complete binary tree)이다

히프의 종류

최대 히프: 부모노드의 키값 >= 자식노드의 키값

최소 히프: 부모노드의 키값 <= 자식노드의 키값

우리는 편의상 최대히프만 다룰 것~

 

히프의 구현

히프를 저장하는 표준적인 자료구조: 배열

-인덱스0은 사용X

-노드 번호 변화 X

-배열을 사용하면 완전 이진 트리에서처럼 자식노드와 부모노드를 쉽게 알 수 있다

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

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

 

9.4 히프의 구현

히프의 정의

#define MAX_ELEMENT 200

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

삽입연산

(1)일단 가장 마지막 위치에 삽입한다

(2)부모노드와 비교->자식이 더 크면 교환

(3)그 다음 부모노드와 비교->자식이 더 크면 교환

(4)그 다음 부모노드와 비교->부모가 더 크면 더이상 교환하지 않는다

 

-실제 구현에서는 바로 휙휙 교환하진 않는다. 그냥 부모 노드만 끌어내린 다음, 삽입될 위치가 확실해진 다음에 최종적으로 새로운 노드가 그 위치로 이동한다.

 

삭제연산

(1)루트노드를 삭제하고 그 자리에 히프의 마지막 노드를 가져온다

(2)새로운 루트와 자식들을 비교해서 자식 중에 더 큰 값과 교환이 일어난다.

(3)그 다음 자식들과도 비교한다

 

히프의 복잡도 분석

삽입, 삭제 모두 최악의 경우 가장 아래 레벨까지 내려가야 하므로 시간복잡도는 O(log2(n))

 

9.5 히프 정렬

최대히프를 이용하면 정렬할 수 있다. n개의 요소는 O(nlog2(n))시간 안에 정렬된다

(1)배열되지 않은 정렬을

(2)최대 히프에 하나씩 추가하며 정렬(=히프정렬)

(3)한 번에 하나씩 히프에서 요소를 꺼내서 배열의 뒤쪽부터 저장 -> 오름차순으로 정렬됨

 

히프정렬의 복잡도

히프트리의 전체 높이가 거의 log2n(완전이진트리이므로)이므로 전체적으로 O(nlog2n)의 시간이 걸린다.

정렬알고리즘이 O(n^2) 걸리는 것에 비해 좋은 편이다.

히프정렬이 최대로 유용한 경우는 전체 자료 정렬이 아닌 가장 큰 값 몇 개만 필요한 때이다

 

9.6 머쉰 스케줄링

머신 스케줄링: 모든 기계를 풀가동하여 가장 최소의 시간 안에 작업들을 모두 끝내는 것

 

LPT(Longest Processing Time first)

-가장 긴 작업을 우선적으로 기계에 할당

-이때는 최대 히프가 아닌 최소히프 사용

9.7 허프만 코드