Heap Sort

개념

• 우선순위 Queue에 Heap을 사용하면 가장 높은 우선 순위를 가진 요소를 제거할 수 있는 점을 활용해 정렬을 실시
• Heap에 따라 값을 삽입O(n * log₂n)하고 반복적으로 Heap이 빌 때까지 제거O(n * log₂n)하면 정렬된 결과물을 얻을 수 있음 → 2 * O(n * log₂n) = O(n * log₂n)

구현

void heapSort(int a[], int n)
{
    MaxHeap h;
    for (int i = 0; i < n; i++)
        h.insert(a[i]);

    // In a max heap, the largest value is returned when deleted,
    // so to sort in ascending order, we fill the array from the end toward the front
    // with the deleted elements.
    for (int i = n - 1; i >= 0; i--)
        a[i] = h.remove().getKey();
}

• 정렬할 배열과 해당 배열의 크기를 입력
• 입력된 크기만큼 Heap에 값을 삽입하고 제거하며 정렬을 실행

Huffman Coding

개념

• 특정 문서에서 어떤 글자의 사용 빈도를 안다면, Binary Tree를 활용해 문서를 압축할 수 있음
• 기존 ASCII 방식은 모든 글자가 같은 개수의 비트를 할당 받으므로 압축에 효율적이지 않음
• Huffman 방식은 자주 사용된 글자에 더 적은 비트 개수를 할당함으로써 문서 용량을 줄일 수 있음
• ASCII와 같은 Fixed-Length Code는 읽을 때 일정한 간격에 따라 읽거나 쓸 수 있음
• 그러나 Huffman 방식과 같은 Variable-Length Code는 할당된 비트를 알려줄 Table을 따라 해석해야함(한 비트씩 확인하면서 일치하는 문자가 있는지 확인)

구현

1. 모든 글자의 사용 빈도를 파악. 각각의 글자는 독립적인 Tree의 root가 됨
2. 가장 적은 빈도를 가지는 2 글자를 결합해 새로운 Binary Tree를 생성. 새로운 root 노드가 만들어지고 해당 노드는 앞선 2 글자를 자식 노드로 취함
3. 새로 추가된 노드를 포함해서 가장 작은 값을 가지는 노드를 찾아 결합 (해당 과정을 반복)
4. 하나의 root를 통해 Binary Tree를 구성
5. 왼쪽 노드는 1을 오른쪽 노드는 0을 할당해 비트 값을 할당
   (비트의 개수는 Tree 내에서 위치한 레벨에 따라 결정됨)

• 해당 과정에서 가장 적은 빈도를 가지는 노드들이 먼저 결합하므로 가장 낮은 레벨을 가지며 가장 큰 비트 개수를 할당받음