우선순위 큐(priority queue)

◦우선순위를 가진 항목들을 저장하는 큐

◦FIFO 순서가아니라우선순위가높은데이터가먼저인출

◦가장 일반적인 큐: 스택이나FIFO 큐를 우선순위 큐로 구현가능

보통의 큐처럼 동작하지만“우선순위” 속성을 갖는 데이터를 다룬다.

1. 삽입연산

2. 제거연산

우선순위 큐 ADT

가장중요한연산은insert 연산(요소삽입), delete 연산(요소 삭제)이다.

우선순위 큐는 2가지로 구분

◦최소 우선순위 큐

◦최대 우선순위 큐

우선순위 큐 구현방법

1. 배열을 이용한 우선순위 큐

2. 연결리스트를 이용한 우선순위 큐

3. 히프(heap)를 이용한 우선순위 큐

히프(heap)란?

○ 히프란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전 이진트 리 ○ 최대 히프(max heap)

⊙ 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 ⊙ key(부모노드) ≥ key(자식노드)

○ 최소 히프(min heap)

⊙ 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리

⊙ key(부모노드) ≤key(자식노드)

히프의 구현방법

○ 히프는 배열을 이용하여 구현

⊙ 완전 이진트리이므로 각 노드에 번호를 붙일 수 있다

⊙ 이 번호를 배열의 인덱스라고 생각

○ 부모노드와 자식노드를 찾기가 쉽다.

⊙ 왼쪽 자식의 인덱스 = (부모의 인덱스)*2

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

허프만 코드

○ 이진 트리는 각 자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용될 수 있다.

○ 이런 종류의 이진트리를 허프만 코딩 트리라고 부른다.

글자의 빈도수

○ 예를 들어보자. 만약 텍스트가 e, t, n, i, s의 5개의 자로만 이루어졌다고 가정하고 각 자의 빈도수가 다음과 같다고 가정하자.

○ 빈도수를 고려하지 않으면 45개 자에 대해 일률적으로 3비트를 할당해야 하므로 45*3=135 비트가 필요하다

○ 하지만, 빈도수를 고려한 Huffman 코딩을 하면 88비트로 표현이 가능하다.

허프만 코드 생성 절차