14. 히프와 우선순위 큐.

Presentation on theme: "14. 히프와 우선순위 큐."— Presentation transcript:

1 14. 히프와 우선순위 큐

2 14.1 히프 히프의 정의 히프화(heapify) 연산
리프-루트 경로를 따라가는 모든 키가 오름차순으로 되어 있는 완전 이진 트리 이러한 순서에 대한 제약은 어떤 키도 부모보다 크지 않다고 말하는 것과 동일함 이것은 히프를 그것의 키에 대한 ≤ 관계를 가지는 부분 순서로 만듦 히프화(heapify) 연산 히프 특성을 만족하도록 시이퀀스의 원소들을 재배열함 리프-루트 경로를 따라 인접해 있는 두 개 이상의 원소를 회전시킴

3 14.2 히프 알고리즘 히프화 연산 알고리즘 1. temp=x로 설정. 2. x가 리프가 아닌 동안, 단계 3-4를 수행.
3. y를 x의 큰 자식으로 설정. 4. 만일 y.key > x.key이면 단계 5-6을 수행. 5. y를 x로 복사. 6. x=y로 설정. 7. temp를 x로 복사.

4 히프화 경로

5 히프화 메소드 LISTING 14.1: The heapify() Method
1 void heapify(int[] a, int i, int n) { 2 int ai = a[i]; 3 while (i < n/2) { // a[i] is not a leaf 4 int j = 2*i + 1; // a[j] is ai’s left child 5 if (j+1 < n && a[j+1] > a[j]) ++j; // a[j] is ai’s larger child 6 if (a[j] <= ai) break; // a[j] is not out of order 7 a[i] = a[j]; // promote a[j] 8 i = j; // move down to next level 9 a[i] = ai; 10 }

6 히프 구축 알고리즘 ALGORITHM 14.2: The Build Heap Algorithm 입력 : 완전 이진 트리 T.
   2. 왼쪽 서브트리에 대해 히프 구축 알고리즘 적용.    3. 오른쪽 서브트리에 대해 히프 구축 알고리즘 적용.    4. 루트에 대해 히프화 알고리즘 적용.

7 트리에 있는 각각의 내부 노드에 적용되는 히프화 연산

8 히프 구축 메소드 LISTING 14.2: The buildHeap() Method
1 void buildHeap(int[] a, int i, int n) { 2 if (i >= n/2) return; 3 buildHeap(a, 2*i+1, n); 4 buildHeap(a, 2*i+2, n); 5 heapify(a, i, n); 6 }

9 14.3 우선순위 큐 정의 원소의 우선순위에 삭제 연산이 수행되는 큐
어떤 것이 높은 우선순위를 가지는지 결정하기 위해 원소들 간의 비교가 가능하다는 것을 가정하고 있음 만일 일반적인 큐를 선입선출(first-in, first-out) 자료 구조(FIFO)로 생각한다면, 우선순위 큐는 최적입선출(best-in, first-out)인 자료 구조(BIFO)로 생각할 수 있음

10 PriorityQueue ADT 연산 우선순위 큐는 BIFO 접근 프로토콜을 유지하는 원소의 컬렉션임
1. Add: 주어진 원소를 큐에 삽입한다. 2. Best: 큐가 공백이 아니면, 최고 우선순위를 가지는 원소를 리턴한다. 3. RemoveBest: 큐가 공백이 아니면, 최고 우선순위를 가지는 원소를 삭제해서 리턴한다. 4. Size: 큐에 있는 원소의 수를 리턴한다. PriorityQueue ADT의 인터페이스

11 PriorityQueue 인터페이스 LISTING 14.3: A PriorityQueue Interface
1 public interface PriorityQueue { 2 public void add(Object object); 3 // POSTCONDITION: the given object is in this queue; 5 public Object best(); 6 // RETURN: the highest priority element in this queue; 7 // PRECONDITION: this queue is not empty; 9 public Object removeBest(); 10 // RETURN: the highest priority element in this queue; 11 // PRECONDITION: this queue is not empty; 12 // POSTCONDITION: the returned object is not in this queue; 14 public int size(); 15 // RETURN: the number of elements in this queue; 16 }

12 우선순위 큐에 80을 삽입

13 삽입 알고리즘 우선순위 큐를 위한 삽입 알고리즘 입력 : 완전 이진 트리 T와 새로운 노드 x. 후조건 : x가 T에 삽입됨.
1. 만일 T가 공백이면, T를 다시 x를 포함하는 단독 트리로 만들고, 리턴. 2. T의 마지막에 새로운 노드를 추가. 3. y=z.parent로 설정. 4. y.key<x.key인 동안, 단계 5-6을 수행. 5. z.key=y.key로 설정. 6. 만일 y가 루트가 아니라면, 단계 7-8을 수행. 7. z=y로 설정. 8. y=y.parent로 설정. 9. y.key=x.key로 설정하고 리턴.

14 HeapPriorityQueue 클래스 (1)
LISTING 14.4: A HeapPriorityQueue Class 1 public class HeapPriorityQueue implements PriorityQueue { 2 private static final int CAPACITY = 100; 3 private Comparable[] a; 4 private int size; 5 6 public HeapPriorityQueue() { 7 this(CAPACITY); 8 } 9 10 public HeapPriorityQueue(int capacity) { 11 a = new Comparable[capacity]; 12 } 13

15 HeapPriorityQueue 클래스 (2)
14 public void add(Object object) { 15 if (!(object instanceof Comparable)) 16 throw new IllegalArgumentException(); 17 Comparable x = (Comparable)object; 18 if (size == a.length) resize(); 19 int i = size++; 20 while (i > 0) { 21 int j = i; i = (i-1)/2; 23 if (a[i].compareTo(x) >= 0) { 24 a[j] = x; return; 26 } 27 a[j] = a[i]; 28 } 29 a[i] = x; 30 }

16 HeapPriorityQueue 클래스 (3)
32 public Object best() { 33 if (size == 0) throw new java.util.NoSuchElementException(); 34 return a[0]; 35 } 37 public Object remove() { 38 Object best = best(); 39 a[0] = a[--size]; 40 heapify(0, size); 41 return best; 42 } 44 public int size() { 45 return size; 46 } 48 public String toString() { 49 if (size == 0) return "{}"; 50 StringBuffer buf = new StringBuffer("{" + a[0]); 51 for (int i = 1; i < size; i++) 52 buf.append("," + a[i]); 53 return buf + "}"; 54 }

17 HeapPriorityQueue 클래스 (4)
56 private void heapify(int i, int n) { 57 Comparable ai = a[i]; 58 while (i < n/2) { 59 int j = 2*i+1; 60 if (j+1 < n && a[j+1].compareTo(a[j]) > 0) ++j; 61 if (a[j].compareTo(ai) <= 0) break; 62 a[i] = a[j]; 63 i = j; 64 } 65 a[i] = ai; 66 } 68 private void resize() { 69 Comparable[] aa = new Comparable[2*a.length]; 70 System.arraycopy(a, 0, aa, 0, a.length); 71 a = aa; 72 } 73 }

18 HeapPriorityQueue 클래스의 테스팅 (1)
LISTING 14.5: Testing the HeapPriorityQueue Class 1 public class TestHeapPriorityQueue { 3 public TestHeapPriorityQueue() { 4 PriorityQueue queue = new HeapPriorityQueue(); 5 int[] pages = {7,3,2,8,3,4,1,3}; 6 for (int i = 0; i < pages.length; i++) { 7 queue.add(new PrintJob(null, pages[i])); 8 System.out.println("queue: " + queue); } 10 while (queue.size() > 0) { 11 System.out.println("queue.remove(): " queue.remove()); 12 System.out.println("q: " + queue); } } 16 public static void main(String[] args) { 17 new TestHeapPriorityQueue(); } 19 }

19 HeapPriorityQueue 클래스의 테스팅 (2)
21 class PrintJob implements Comparable { 22 private java.io.File file; 23 private int pages; 24 private String id; 25 private static int n = 100; 27 public PrintJob(java.io.File file, int pages) { 28 this.file = file; 29 this.pages = pages; 30 this.id = "ID" + n++; 31 } 33 public int compareTo(Object object) { 34 if (!(object instanceof PrintJob)) 35 throw new IllegalArgumentException(); 36 PrintJob that = (PrintJob)object; 37 return that.pages - this.pages; 38 } 40 public String toString() { 41 return id + "(" + pages + ")"; } 43 }

20 출력 출력 결과 q: {ID100(7)} q: {ID101(3),ID100(7)}
q: {ID102(2),ID100(7),ID101(3)} q: {ID102(2),ID100(7),ID101(3),ID103(8)} q: {ID102(2),ID104(3),ID101(3),ID103(8),ID100(7)} q: {ID102(2),ID104(3),ID101(3),ID103(8),ID100(7),ID105(4)} q: {ID106(1),ID104(3),ID102(2),ID103(8),ID100(7),ID105(4),ID101(3)} q: {ID106(1),ID104(3),ID102(2),ID107(3),ID100(7),ID105(4),ID101(3),ID103(8)} queue.remove(): ID106(1) q: {ID102(2),ID104(3),ID101(3),ID107(3),ID100(7),ID105(4),ID103(8)} queue.remove(): ID102(2 q: {ID104(3),ID107(3),ID101(3),ID103(8),ID100(7),ID105(4)} queue.remove(): ID104(3) q: {ID107(3),ID105(4),ID101(3),ID103(8),ID100(7)}queue.remove(): ID107(3) q: {ID101(3),ID105(4),ID100(7),ID103(8)}queue.remove(): ID101(3) q: {ID105(4),ID103(8),ID100(7)}queue.remove(): ID105(4) q: {ID100(7),ID103(8)}queue.remove(): ID100(7) q: {ID103(8)}queue.remove(): ID103(8) q: {}

21 14.5 사례 연구: 허프만 코드 자료 압축 정보의 손실 없이 본래의 파일 크기보다 작은 파일로 압축
저장소의 사용 및 통신에 유리 영문자의 인코딩 : 고유의 비트 스트링으로 표기 7 비트 사용 (ASCII) 8 비트 parity bit 추가 EBCDIC “TREE” : 32 bit 사용

22 허프만 코드 문서를 인코딩하는 최적의 알고리즘
이 알고리즘은 가장 자주 나타나는 문자가 가장 짧은 코드를 갖도록 문자에 이진 코드를 부여하는데, 이것은 텍스트 문서를 최소 길이로 인코딩함 탐색 길이의 기대값을 감소시키기 위하여 가장 자주 읽는 노드를 가능한 한 루트에 가깝게 놓는다. 허프만 코드(Huffman code)는 팩스, 모뎀, 컴퓨터 네트워크, 고해상도 텔레비전(high-definition television) 등의 실제적인 응용에 널리 사용되고 있음 prfix constraint 인코딩된 문자의 전위 비트 표기(prefix)가 인코딩된 다른 문자의 전체 비트 표기와 같아서는 안된다. 예 : ‘A’가 ‘1001’이고 ‘M’의 비트 표기가 ‘ ’이면 이거만 읽어서는 ‘A’의 비트 표기인지 ‘M’의 전위 비트 표기인지 분별할 수 없다.

23 허프만 코드 생성 과정 문서를 위한 허프만 코드는 문서에 나타나는 서로 다른 문자에 대해 각각 하나의 리프를 갖는 우선순위 큐로부터 생성됨 각각의 문자에 대한 코드는 그 문자에 대한 루트-리프 경로에 의해 결정되는데, 왼쪽 가지는 “0”으로 표시되고, 오른쪽 가지는 “1”로 표시됨 오른쪽-왼쪽-오른쪽으로 가는 루트-리프 경로는 코드 101로 정해짐

24 허프만 코드의 예

25 허프만 알고리즘 빈도수 테이블 최소 히프 허프만 트리 허프만 코드

26 허프만 코드의 생성 허프만 코드 생성 알고리즘 입력 : 문자의 시이퀀스. 출력 : 입력 문자에 대한 비트 코드.
후조건 : 비트 코드가 유일 접두부 특성을 가지고 최적임. 1. 입력 문자에 대한 빈도수 표를 작성. 2. 최소 우선순위 큐에 문자-빈도수 쌍을 적재. 3. 우선순위 큐로부터 허프만 트리 구성. 4. 루트-리프 경로 상의 비트 시이퀀스로 각각의 리프에 있는 문자를 인코드.

27 인코딩 디코딩 두 문자에 대한 인공적인 문자를 만듬 이진 트리 : 가지는 0과 1로 표기 단말 노드 : 문자를 나타냄
011 01 00 010 인코딩 두 문자에 대한 인공적인 문자를 만듬 인공적인 문자의 빈도수는 두 문자의 빈도수의 합 빈도수가 작은 문자가 루트로부터 가장 멀리 떨어지게 구성 빈도수가 가장 작은 두 문자 Ci와 Cj를 선택하여 인공적인 문자 Cij를 만듬 : fij= fi+fj 디코딩 이진 트리 : 가지는 0과 1로 표기 단말 노드 : 문자를 나타냄 루트로부터 단말 노드로의 순회

28 Huffman_Encoding(S, f)
{ /* Input: S(a string of charaters), f(an array of frequency) Output : T(The Huffman tree for S) */ insert all characters into a heap H according to their frequencies; while (H is not empty) { if (H contains only one character X) make X the root of T; else { pick two characters X and Y with lowest frequencies and delete them; replace X and Y with a new character Z whose frequency is the sum of the frequencies of X and Y; insert Z into H; make X and Y children of Z in T; /* Z has no parent yet */ }

29 예제 텍스트는 A, B, C, D, E, F로 구성되어 있고 각각의 빈도수는 5, 2, 3, 4, 10, 1이다. 4 E A