[자료구조] 우선순위 힙 -3

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

허프만 코딩

• 입력 파일의 문자 빈도 수로 최소힙을 이용하여 허프만 코드를 만들어 파일을 압축하고 나중에 복원하는 알고리즘
  
• 빈도 수가 높은 문자에는 짧은 코드를 부여하고, 빈도 수가 낮은 문자에는 긴 코드를 부여하여 압축 효율을 높인다
  
• Unix의 파일 압축 명령어인 compress에 사용. jpeg 이미지 파일과 mp3 음악 파일을 압축하기 위한 서브루틴으로도 활용
  
  

• 수행 단계
  
  1. 입력파일을 스캔하여 각 문자의 빈도수를 계산하고, 이 빈도수로 허프만 트리를 생성한다
     
  2. 트리로부터 각 문자에 대응하는 허프만 코드를 추출
     
  3. 파일을 스캔하며 각 문자를 허프만 코드로 변환
     
     
• 허프만 트리 생성 알고리즘
  1) 입력 파일을 스캔하여 각 문자의 빈도 수 계산
  2) 빈도 수를 우선순위로 최소힙 h를 구성
  3) 아래 코드 참조
  
  

  while (힙의 크기 > 1) {
    e1 = h.delete_min();
    e2 = h.delete_min();
    t = new 항목(e1의 빈도 수 + e2의 빈도 수, left = e1, left = e2);
    h.insert(t); // 힙에 새로 만든 항목 삽입
  }
  return h.delete_min();
  

기타 우선순위 큐

Leftist 힙

• 왼쪽으로 치우치다
  
• Leftist 트리의 구조를 가진 힙
  
• 이진힙의 속성과 동일
  
• npl(x의 왼쪽 자식노드) >= npl(x의 오른쪽 자식노드)의 관계를 만족한다
  
• 각 연산을 O(logN) 시간에 수행하기 위하여, 트리를 왼쪽으로 치우친 형태로 만든다.
  
• 왼쪽으로 치우친 트리 구조는 루트노드로부터 계속해서 오른쪽 방향으로만 내려가서 만나는 null까지의 경로 길이를 logN이 넘지 않게 만든다
  
  

Skew 힙

• 구조적 제약이 없는 단순한 자료구조
  
• 각 노드의 npl을 계산할 필요 없고, 자식노드들의 npl을 비교할 필요도 없음
  
• Left힙과 같이 rightmost 경로를 따라 combine 연산을 수행하는데, 다만 루트 방향으로 거슬러 올라가며 무조건 현재 노드의 좌우 서브트리를 교환
  
• 스스로 조절하는 힙으로도 부름
  
• 조건 없이 서브트리를 교환하여 저절로 왼쪽으로 치우친 형태를 유지하게 만든다
  
  

이항힙

• 이항 힙은 노드들이 힙의 속성을 만족하는 이항트리들로 구성
  
• 이진트리의 형태에서 벗어나 여러 개의 트리들로 힙을 만듬
  
• 이항 힙은 유일한 차수를 가진 이항트리들로만 구성되어야 함
  
  

요약

• 우선순위큐는 가장 높은 우선순위를 가진 항목에 접근, 또는 삭제하는 연산과 삽입 연산을 지원
  
• 이진힙은 완전이진트리로서 부모의 우선순위가 자식의 우선순위보다 높은 자료구조
  
• 허프만 코딩은 빈도 수가 높은 문자에 짧은 이진코드를 부여하고, 빈도 수가 낮은 문자에 긴 이진코드를 부여하여 압축 효율을 높인다
  
• 허프만 알고리즘은 최악의 경우는 입력 파일의 문자들이 모두 같은 빈도 수를 갖는 경우이고, 파일에 문자들의 빈도 수가 고르지 않게 분포할 때 우수한 압축 성능을 보임
  
• Leftist 힙은 왼쪽 부분으로 치우친 구조를 가지며, 그 이유는 rightmost 경로의 길이를 logN보다 크지 않게 하기 위함
  
• Skew 힙은 구조적 제약조건이 없으며 무조건 현재 노드의 좌우 서브트리를 교환
  
• 이항힙은 노드들이 힙의 속성을 만족하는 이항트리들로 구성
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/xcnNShLYQ3A