우선순위 큐(priority queue)
◦우선순위를 가진 항목들을 저장하는 큐
◦FIFO 순서가아니라우선순위가높은데이터가먼저인출
◦가장 일반적인 큐: 스택이나FIFO 큐를 우선순위 큐로 구현가능
보통의 큐처럼 동작하지만“우선순위” 속성을 갖는 데이터를 다룬다.
- 삽입연산
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비트로 표현이 가능하다.
허프만 코드 생성 절차