알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 2016. 09. 13 하 상 호

우선순위 큐 우선순위 큐(priority queue): 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 가장 일반적인 큐: 스택이나 FIFO 큐를 우선순위큐로 구현할 수 있다.    자료구조    삭제되는 요소    스택    가장 최근에 들어온 데이터    큐    가장 먼저 들어온 데이터    우선순위큐    가장 우선순위가 높은  데이터 응용분야: 시뮬레이션 시스템(여기서의 우선 순위는 대개 사건의 시각이다.) 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링

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

우선순위큐 구현방법(1) 배열을 이용한 우선순위큐 정렬되어 있지 않은 경우 삽입: 삭제: 정렬되어 있는 경우

우선순위큐 구현방법(2) 연결리스트를 이용한 우선순위큐 리스트를 정렬하지 않은 경우 리스트를 정렬하는 경우 삽입: 삭제: 표현   방법 삽    입 삭    제  순서없는 배열  O(1)  O(n)  순서없는 연결 리스트  정렬된 배열  정렬된 연결 리스트  히프  O(logn) 알고리즘 복잡도? 알고리즘 복잡도?

우선순위큐 구현방법(3) 히프(heap)를 이용한 우선순위큐 우선순위 큐 구현 방법 n = 1000일 때, ? 표현 방법 표현   방법 삽    입 삭    제  순서없는 배열  O(1)  O(n)  순서없는 연결 리스트  정렬된 배열  정렬된 연결 리스트  히프  O(logn) n = 1000일 때, ?

히프(heap)란? 개념: 히프란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 구성된 자료구조 히프는 데이터들을 느슨한 상태로 정렬 전체 항목을 정렬하지 않고 최대나 최소 값만을 루트에 위치 히프란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리 Key(parent) >= key(child) 또는 Key(parent) <= key (child)

히프(heap) 정의 최대 히프(max heap) 최소 히프(min heap) 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 key(부모노드) ≥key(자식노드) 최소 히프(min heap) 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리 key(부모노드) ≤key(자식노드)

Heap의 ADT 데이터: heap 트리 (key(parent) >= key (child), 최대 히프경우) 연산 Heap: 히프, item: 항목 createHeap() := init(heap) := isEmpty(heap):= isFull(heap):= insertHeap(heap, item):= deleteHeap(heap) :=

히프의 구현(1) 히프는 배열을 이용하여 구현 부모노드와 자식노드를 찾기가 쉽다. 완전이진트리이므로 각 노드에 번호를 붙일 수 있다 이 번호를 배열의 인덱스라고 생각 부모노드와 자식노드를 찾기가 쉽다. 왼쪽 자식의 인덱스 = 오른쪽 자식의 인덱스 = 부모의 인덱스 = 왼쪽 자식노드 방문은?

히프에서의 삽입 히프에 있어서 삽입 연산은 회사에서 신입 사원이 들어오면 일단 말단 위치에 앉힌 다음에, 신입 사원의 능력을 봐서 위로 승진시키는 것과 비숫 히프에 새로운 요소가 들어 오면, 일단 새로운 노드를 히프의 마지막 노드에 이어서 삽입 삽입 후에 새로운 노드를 부모 노드들과 교환해서 히프의 성질을 만족

heap 삽입 연산 예(1) 새로운 노드 n을 히프의 마지막 위치에 삽입 위의 과정을 반복 노드 8 삽입

heap 삽입 연산 예(2) 다음 히프에 대해서 노드 10을 삽입하라.

히프에서의 삭제 최대히프에서의 삭제는 가장 큰 키값을 가진 노드를 삭제하는 것을 의미 삭제 연산은 회사에서 사장의 자리가 비게 되면 먼저 제일 말단 사원을 사장 자리로 올린 다음에, 능력에 따라 강등시키는 것과 비슷하다. 루트노드를 삭제한다 마지막노드를 루트노드로 이동한다. 루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 히프 성질을 만족시킨다.

Heap 삭제의 예 (1) 루트 노드 삭제 히프의 마지막 노드를 루트에 배치 히프 성질 유지: 부모, 자식 비교하여 이동 : 자식중에서 큰 노드와 부모를 교환

Heap 예제 다음 숫자들을 순차적으로 읽어들여서 최대 히프 트리를 구성하라. 10, 40, 30, 5, 12, 6, 15, 9, 60 위에서 구성된 히프 트리에서 가장 큰 값을 갖는 노드 3개를 순차적으로 삭제하라.

Heap 예제 (2) 히프 트리가 다음과 같이 저장되어 있다. 여기에 11을 삽입하라. 인덱스: 1 2 3 4 5 6 7 8 데이터: 12 10 8 4 6 2 5 3 위에서 구성된 히프 트리에서 가장 큰 값을 갖는 노드를 삭제하라.

Heap 삽입 알고리즘 insertHeap(heap: Heap, item: element) { if (isFull(heap)) then error heapSize <- heapSize + 1 // 현재 히프 크기를 증가` // 새로 추가될 노드 위치 // heapSize는 현재 히프의 크기 표현 i <- heapSize; // 현재 삽입 위치 // 히프 성질이 만족될 때까지 삽입 위치를 위로 이동하여 조정 heap[i] <- item; // 삽입 위치에 항목 저장 }

Heap 삭제 알고리즘 deleteHeap(heap: Heap) { if (isEmpty(heap)) then return error; // 공백 히프 item <- heap[1]; // 히프의 ? 원소 temp <- heap[heapSize]; // 히프의 ? 원소 heapSize <- heapSize – 1; i <- 1; // 마지막 원소가 이동될 현재 위치 j <- 2; // i의 왼쪽 자식 노드 // temp가 이동될 히프상의 위치를 찾아 이동한다. heap[i] <- temp; return item; }

히프의 C 언어 구현 1차원 배열로 히프 표현 #define MAX_ELEMENT 200 typedef int element; typedef struct { element heap[MAX_ELEMENT]; int heapSize; } heapType; * 삽입, 삭제, 예제 프로그램 참고(교재 프로그램 8.1 - 8.3)

히프의 응용: 히프 정렬 히프를 이용하면 정렬 가능 먼저 정렬해야 할 n개의 요소들을 최대 히프에 삽입 한번에 하나씩 요소를 히프에서 삭제하여 저장하면 된다. 삭제되는 요소들은 값이 증가되는 순서(최소 히프의 경우) 히프 정렬이 최대로 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다. 이렇게 히프를 사용하는 정렬 알고리즘을 히프 정렬이라고 한다.

히프정렬 프로그램 void heapSort(element a[], int n) { // 우선 순위 큐인 히프를 이용한 정렬 // 주어진 배열을 정렬하시오. // 여러분은 히프 정렬을 사용해야 한다. void heapSort(element a[], int n) { // 배열 a에 포함된 원소들을 꺼내어 순서대로 히프 트리에 삽입한다. // h로부터 순서대로 노드를 삭제하여 a에 저장한다. }

히프 응용: 아이스크림 가게 시뮬레이션 프로그램 8.5 참고 가게에는 다음 3가지 이벤트가 발생 Arrival: 손님 도착 Order: 메뉴 주문 Leave: 손님이 떠남 각 이벤트 발생시마다 이벤트를 우선순위 큐에 삽입하고, 가장 먼저 발생한 이벤트 순으로 이벤트를 처리한다. Arrival는 order 이벤트 생성하고, order 이벤트는 leave 이벤트 생성하고, leave 이벤트는 가게의 빈 자리수를 증가시킨다. 손님이 착석이 가능한 경우에만 arrival 이벤트를 처리한다. 이벤트는 다음과 같이 표현 typedef struct { int type; // 이벤트 종류 int time; // 이벤트가 일어난 시각 int number; // 고객 숫자 } event; 우선순위큐에서 이벤트가 발생한 시각순으로 이벤트를 꺼내어처리한다. 우선순위큐가 비어 있으면 프로그램은 종료한다.

히프 응용: 아이스크림 가게 시뮬레이션 소스 코드(프로그램 8.6, pp. 336)