자료구조 - 힙(Heap)

힙(Heap) 이란

힙은 특별한 종류의 이진트리인데, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다.

힙은 다음과 같은 특성을 가지고 있습니다.

1. 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작음(최대 힙 또는 최소 힙).
2. 완전 이진 트리(Complete Binary Tree) 구조를 가짐. 이는 트리의 모든 레벨이 완전히 채워져 있고, 가장 아래 레벨은 왼쪽부터 채워져야 함을 의미합니다.

 

힙은 주로 다음과 같은 작업에 사용됩니다.

• 최댓값 또는 최솟값을 빠르게 찾아내는 작업 (O(1) 시간 복잡도로 가능).
• 데이터의 삽입과 삭제(최대 또는 최소 요소에 대한)를 빠르게 수행하는데 효율적.

최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지며, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 이러한 힙의 특성은 다양한 응용 분야에서 사용되며, 우선순위 큐나 정렬 알고리즘 등에 활용됩니다.

 

힙 자료구조 예시 설명

예시를 통해 힙 구조를 더 자세히 설명해 드리겠습니다.

최대 힙(Max Heap)을 사용하여 숫자의 집합을 관리한다고 가정해 봅시다. 최대 힙은 루트 노드가 가장 큰 값을 가지며, 각 부모 노드는 자식 노드보다 크거나 같은 값을 가지는 이진트리입니다.

1. 먼저, 힙은 비어 있습니다.

힙: []

2. 숫자 10을 힙에 추가합니다. 힙은 아래와 같이 구성됩니다.

힙: [10]

3. 숫자 7을 추가하면 힙은 다음과 같이 구성됩니다.

힙: [10, 7]

4. 숫자 15를 추가하면 힙은 아래와 같이 재구성됩니다.

힙: [15, 7, 10]

5. 숫자 5를 추가하면 힙은 다시 재구성됩니다.

힙: [15, 7, 10, 5]

6. 이제 최대 힙에서 최댓값을 추출하면, 루트 노드의 값인 15가 반환됩니다. 그리고 힙은 다음과 같이 재구성됩니다.

힙: [10, 7, 5]

7. 마찬가지로 다시 최댓값을 추출하면 10이 반환되고 힙은 다시 재구성됩니다.

힙: [7, 5]

 

이와 같이 최대 힙을 사용하면 항상 루트 노드에는 가장 큰 값이 유지되며, 값을 추가하거나 제거할 때마다 힙이 재구성되어 이러한 특성을 유지합니다. 이를 통해 최대값을 빠르게 찾아낼 수 있고, 우선순위 큐 등 다양한 응용 분야에서 활용할 수 있습니다. 최소 힙의 경우도 비슷한 원리로 동작하지만, 루트 노드에는 가장 작은 값이 유지됩니다.