priority queue
![[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcT2Dxb%2FbtqSATggBLA%2FCIBeKSLq0s6MDTNVM345Jk%2Fimg.png)
[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)
1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 1.2 힙이란? 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태) 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 힙의 종류 최대 힙 (Max Heap) ..
![[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbhideE%2FbtqF1noe0pu%2FrhMNuzGFtW9aSfruJ8T1hk%2Fimg.png)
[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현
허프만 부호화 (Huffman coding) 허프만 부호화란 무손실 압축에 사용되는 엔트로피 코딩 중 하나이다. 이전 글에서 엔트로피 코딩의 목적은 데이터 심볼 당 평균 부호 길이가 엔트로피에 가까워지도록 부호를 할당하여 압축 효율을 높이는 것이라고 하였다. 허프만 부호화는 발생 빈도가 높은 (자주 나오는) 심볼에는 짧은 부호를 할당하고, 발생 빈도가 적은 심볼에는 비교적 긴 부호를 할당한다. 따라서 최대한으로 평균 부호길이가 압축되는 결과를 얻을 수 있다. 허프만 부호화 시 각각의 심볼에 접두 코드(Prefix code)를 할당한다. 접두 코드란 코드 집합에서 어떤 코드도 다른 코드의 접두사가 되지 않게 만들어진 코드이다. 예를 들어 {"0", "01"} 코드 집합의 경우 접두 코드가 아니다. "0"은..