최대 힙과 최소 힙의 정의 / 힙의 삽입, 삭제 연산 방법 / 힙을 응용한 허프만 코드의 특징과 생성 방법

문서 내 토픽

1. 최대 힙과 최소 힙의 정의

힙(heap)이란 피라미드 모양으로 차곡차곡 쌓아 올린 더미 모양을 말한다. 자료구조에서의 힙은 우선순위 큐를 구현하는 자료구조이며 빠르게 가장 크거나 작은 데이터를 찾을 수 있도록 만들어진 자료구조라고 정의할 수 있을 것이다. 최대 힙(Maxheap)이란 부모 노드의 key 값이 자식의 key 값보다 크거나 같은 완전 이진 트리 형식이다. 즉, 루트 노드에 저장된 값이 트리 전체에서 가장 큰 값이 된다. 반대로 최소 힙(Minheap)은 부모 노드의 key 값이 자식의 key 값보다 작거나 같은 완전이진 트리 형식을 말한다. 즉, 루트 노드에 저장된 값이 트리 전체에서 가장 작은 값이 된다.
2. 최대 힙, 최소 힙의 삽입과 삭제 연산 방법

최대 힙의 삽입 연산은 새로 삽입할 원소의 노드를 생성한 후, 완전 이진 트리의 조건을 만족하기 위해 마지막 노드에 삽입한다. 다음으로 삽입되는 노드의 최종 위치를 결정하기 위해 부모 노드의 값과 비교하였을 때 삽입되는 노드의 값이 부모 노드보다 클 때 자리를 바꾸는 과정을 거친다. 최소 힙에서의 삽입 연산 방법도 마찬가지로, 새로 삽입할 원소의 노드를 생성한 후, 완전 이진 트리의 조건을 만족하기 위하여 마지막 노드에 삽입한다. 다음으로 삽입되는 원소의 최종 위치를 결정하기 위해 부모 노드의 값과 비교하였을 때 삽입되는 원소의 값이 부모 노드보다 작을 때 자리를 바꾸는 과정을 거친다. 최대 힙에서의 삭제 연산은 루트 노드가 삭제되면 말단 노드를 루트로 이동시키고 삽입된 노드와 자식 노드의 값을 비교하여 삽입된 노드보다 큰 값을 가진 자식 노드와 자리를 바꾸는 과정을 거친다. 최소 힙에서의 삭제 연산 방법도 마찬가지로 루트 노드가 삭제되면 말단 노드를 루트로 이동시킨 뒤, 삽입된 노드보다 작은 값을 가진 자식 노드와 자리를 바꾸는 과정을 거친다.
3. 허프만 코드의 개념

허프만 코드는 허프만 알고리즘에 의해 생성되었으며, 데이터 전체를 나타내는 정보의 발생확률은 서로 다르게 발생한다는 점에서 착안한 부호화 기법이다. 발생 빈도수가 높은 문자는 짧은 부호를 할당하고 발생 빈도수가 낮은 문자는 긴 부호를 할당하여 발생 빈도수가 많은 코드의 길이를 줄일 수 있어서 전체 데이터의 크기가 줄어들게 된다. 따라서 데이터를 효율적으로 압축하는 것이 가능하다.
4. 힙을 응용한 허프만 코드의 특징과 생성 방법

허프만 코드는 발생 빈도수가 높은 코드의 길이를 줄일 때 사용되는 코드이며, 우리는 힙을 응용하여 허프만 코드를 작성할 수 있다. 먼저 각 문자의 빈도수를 내림차순으로 적은 후, a와 b의 빈도수를 더한 값과 c의 빈도수를 더한 값, d의 빈도수와 e의 빈도수를 더한 값을 더하면 45라는 값이 나온다. 이때 뻗어나가는 각 노드의 왼쪽 영역에는 1을 부여하고, 오른쪽에는 0을 부여하면 a는 111, b는 110, c는 10, d는 01, e는 00으로 상대적으로 빈도수가 높은 문자 c, d, e는 짧은 이진 코드로 표현할 수 있다. 이는 최대 힙을 이용하여 가변 길이 코드로 표현한 것이다.

Easy AI와 토픽 톺아보기

1. 최대 힙과 최소 힙의 정의

최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 이진 트리를 말합니다. 반면 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 이진 트리를 말합니다. 이러한 힙 구조는 우선순위 큐와 같은 자료구조에서 효율적인 삽입과 삭제 연산을 가능하게 합니다. 최대 힙은 최대값을 빠르게 찾을 수 있고, 최소 힙은 최소값을 빠르게 찾을 수 있습니다. 이러한 특성으로 인해 힙은 다양한 알고리즘에서 유용하게 사용됩니다.
2. 최대 힙, 최소 힙의 삽입과 삭제 연산 방법

최대 힙과 최소 힙에서의 삽입과 삭제 연산은 다음과 같습니다. 삽입 시에는 새로운 노드를 트리의 마지막 위치에 추가한 후, 부모 노드와 비교하여 힙 속성을 만족하도록 노드를 재배치합니다. 삭제 시에는 루트 노드(최대 값 또는 최소 값)를 제거하고, 마지막 노드를 루트 노드로 옮긴 후 다시 힙 속성을 만족하도록 노드를 재배치합니다. 이러한 삽입과 삭제 연산은 O(log n) 시간 복잡도를 가지므로 효율적입니다. 힙 구조를 활용하면 우선순위 큐와 같은 자료구조를 구현할 수 있습니다.
3. 허프만 코드의 개념

허프만 코드는 가변 길이 코드로, 문자의 출현 빈도에 따라 각 문자에 대한 코드 길이를 다르게 할당하는 방식입니다. 출현 빈도가 높은 문자는 짧은 코드를, 출현 빈도가 낮은 문자는 긴 코드를 할당합니다. 이를 통해 전체 데이터의 평균 코드 길이를 최소화할 수 있습니다. 허프만 코드는 압축 알고리즘에 널리 사용되며, 데이터 압축 효율이 높은 것이 특징입니다. 또한 허프만 코드는 복호화 과정이 간단하여 실시간 압축/압축 해제가 가능합니다.
4. 힙을 응용한 허프만 코드의 특징과 생성 방법

허프만 코드는 힙 자료구조를 활용하여 생성됩니다. 먼저 각 문자의 출현 빈도를 계산하고, 이를 기반으로 최소 힙을 구성합니다. 그 다음 힙에서 가장 작은 두 개의 노드를 선택하여 새로운 내부 노드를 만들고, 이 내부 노드의 가중치는 두 자식 노드의 가중치 합이 됩니다. 이 과정을 반복하여 최종적으로 하나의 루트 노드가 남게 되면 이것이 허프만 트리가 됩니다. 이 허프만 트리를 이용하여 각 문자에 대한 코드를 생성할 수 있습니다. 허프만 코드는 문자 출현 빈도에 따라 가변 길이 코드를 생성하므로 데이터 압축에 매우 효과적입니다.