14. 히프와 우선순위 큐

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

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로 복사.

히프화 경로

히프화 메소드 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 }

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

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

히프 구축 메소드 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 }

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

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

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 }

우선순위 큐에 80을 삽입

삽입 알고리즘 우선순위 큐를 위한 삽입 알고리즘 입력 : 완전 이진 트리 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로 설정하고 리턴.

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

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 }

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 }

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 }

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); 9 } 10 while (queue.size() > 0) { 11 System.out.println("queue.remove(): " + queue.remove()); 12 System.out.println("q: " + queue); 13 } 14 } 16 public static void main(String[] args) { 17 new TestHeapPriorityQueue(); 18 } 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 + ")"; 42 } 43 }

출력 출력 결과 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: {}

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

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

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

허프만 코드의 예

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

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

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

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 */ }

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