Heap(힙)에 대해서 알아보기

안녕하세요, 여러분! 오늘은 자료구조의 세계에서 매우 중요한 개념인 ‘힙(Heap)‘에 대해 알아보려고 합니다. 힙이라는 말을 처음 들어보시는 분들도 계실 텐데요, 걱정 마세요. 아주 쉽고 재미있게 설명해 드리겠습니다.

먼저, 힙이 무엇인지 간단히 설명드릴게요. 힙은 특별한 규칙을 가진 ‘트리’ 모양의 자료구조입니다. ‘트리’라고 하면 나무를 떠올리셔도 좋아요. 나무의 뿌리부터 시작해서 가지가 뻗어나가는 모양을 상상해 보세요. 자료구조에서의 트리도 이와 비슷한 모양을 하고 있답니다.

힙의 특별한 규칙은 무엇일까요? 바로 ‘부모 노드’와 ‘자식 노드’ 사이의 관계에 있습니다. 힙에는 두 가지 종류가 있어요

최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같습니다.
최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같습니다.

힙은 왜 사용할까요? 힙의 가장 큰 장점은 최댓값이나 최솟값을 빠르게 찾을 수 있다는 것입니다. 최대 힙에서는 항상 루트 노드(가장 위의 노드)가 전체 힙에서 가장 큰 값을 가지고 있고, 최소 힙에서는 루트 노드가 가장 작은 값을 가지고 있죠.

이런 특성 때문에 힙은 다음과 같은 상황에서 유용하게 사용됩니다:

우선순위 큐 구현: 가장 우선순위가 높은 작업을 빠르게 찾아 처리할 수 있습니다.
정렬 알고리즘: 힙 정렬은 힙을 이용한 효율적인 정렬 방법입니다.
그래프 알고리즘: 다익스트라의 최단 경로 알고리즘 등에서 사용됩니다.

힙의 주요 연산에는 어떤 것들이 있을까요?

삽입(Insert): 새로운 원소를 힙에 추가합니다.
삭제(Delete): 루트 노드를 제거하고 반환합니다. 최대 힙에서는 최댓값, 최소 힙에서는 최솟값을 얻을 수 있습니다.

이 연산들이 어떻게 동작하는지 간단히 설명해 드릴게요.

삽입 연산:

새로운 원소를 힙의 마지막 위치에 추가합니다.
새로 추가된 원소를 부모 노드와 비교하면서, 힙의 조건을 만족할 때까지 위로 올립니다.

삭제 연산:

루트 노드를 제거합니다.
힙의 마지막 원소를 루트 위치로 가져옵니다.
새 루트를 자식 노드들과 비교하면서, 힙의 조건을 만족할 때까지 아래로 내립니다.

삽입 연산은 새로운 원소를 아래에서 위로 올리는 과정이고, 삭제 연산은 마지막 원소를 위에서 아래로 내리는 과정입니다.

힙의 이러한 특성 때문에 최댓값이나 최솟값을 빠르게 찾을 수 있어요. 최대 힙에서는 항상 루트 노드가 가장 큰 값을 가지고 있고, 최소 힙에서는 루트 노드가 가장 작은 값을 가지고 있죠.

파이썬에서는 ‘heapq’ 모듈을 통해 최소 힙을 쉽게 구현할 수 있습니다. ‘heapq’는 리스트를 최소 힙처럼 다룰 수 있게 해주는 모듈이에요.

간단한 예제를 통해 ‘heapq’ 모듈의 사용법을 알아볼까요?

import heapq

# 빈 리스트 생성
heap = []

# 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print("힙에 원소 추가 후:", heap)

# 원소 삭제 (최솟값 추출)
min_value = heapq.heappop(heap)
print("추출된 최솟값:", min_value)
print("최솟값 추출 후 힙:", heap)

# 최솟값 확인 (제거하지 않고)
print("현재 최솟값:", heap[0])

# 리스트를 힙으로 변환
numbers = [4, 1, 7, 3, 8, 5]
heapq.heapify(numbers)
print("리스트를 힙으로 변환:", numbers)

이 코드를 실행하면 다음과 같은 결과를 볼 수 있어요

힙에 원소 추가 후: [1, 3, 7, 4]
추출된 최솟값: 1
최솟값 추출 후 힙: [3, 4, 7]
현재 최솟값: 3
리스트를 힙으로 변환: [1, 3, 5, 4, 8, 7]

여기서 주목할 점은 힙의 원소들이 완전히 정렬된 상태는 아니라는 거예요. 대신 부모 노드가 항상 자식 노드보다 작거나 같은 관계만 유지합니다. 이런 특성 덕분에 힙은 원소를 추가하거나 삭제할 때 빠른 속도를 유지할 수 있답니다.

힙은 다양한 알고리즘과 자료구조에서 활용됩니다. 특히 우선순위 큐를 구현할 때 자주 사용되죠. 우선순위 큐는 일반적인 큐와 비슷하지만, 우선순위가 높은 원소가 먼저 나오는 특징이 있어요. 이는 힙의 특성과 잘 맞아떨어지죠.

여러분, 이제 힙에 대해 어느 정도 이해가 되셨나요? 처음에는 조금 복잡해 보일 수 있지만, 실제로 사용해보면 매우 유용한 자료구조라는 것을 느끼실 수 있을 거예요.

힙을 더 잘 이해하기 위해 직접 실습해보는 것은 어떨까요? 예를 들어, 숫자들의 리스트에서 상위 K개의 큰 숫자를 찾는 문제를 풀어보세요. 이런 문제는 최소 힙을 이용하면 효율적으로 해결할 수 있답니다.

예를 들어, 다음과 같은 문제를 생각해볼까요? “주어진 숫자 리스트에서 가장 큰 3개의 숫자를 찾아라.” 이 문제를 힙을 사용해서 해결해보겠습니다.

import heapq

def find_top_k_elements(numbers, k):
    # 최소 힙 생성
    heap = []

    for num in numbers:
        # 힙의 크기가 k보다 작으면 원소 추가
        if len(heap) < k:
            heapq.heappush(heap, num)
        # 힙의 크기가 k이고, 현재 숫자가 힙의 최솟값보다 크면
        elif num > heap[0]:
            # 힙의 최솟값을 제거하고 현재 숫자 추가
            heapq.heapreplace(heap, num)

    # 힙에 남아있는 k개의 원소가 가장 큰 k개의 원소
    return sorted(heap, reverse=True)

# 테스트
numbers = [3, 1, 10, 8, 2, 5, 4, 7, 9, 6]
k = 3

result = find_top_k_elements(numbers, k)
print(f"가장 큰 {k}개의 숫자: {result}")

이 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다

가장 큰 3개의 숫자: [10, 9, 8]

이 알고리즘은 어떻게 작동하는 걸까요? 한 번 자세히 살펴볼까요?

먼저 크기가 k인 최소 힙을 만듭니다.
리스트의 모든 숫자를 순회하면서
- 힙의 크기가 k보다 작으면 숫자를 힙에 추가합니다.
- 힙의 크기가 k이고, 현재 숫자가 힙의 최솟값(루트)보다 크면, 힙의 최솟값을 제거하고 현재 숫자를 추가합니다.
모든 숫자를 순회한 후, 힙에 남아있는 k개의 숫자가 전체 리스트에서 가장 큰 k개의 숫자입니다.

이 방법의 시간 복잡도는 O(n log k)입니다. 여기서 n은 리스트의 길이이고, k는 찾고자 하는 큰 숫자의 개수입니다. 이는 모든 숫자를 정렬하는 방법(O(n log n))보다 더 효율적이죠.

힙은 이처럼 “상위 K개” 또는 “하위 K개”와 같은 문제를 해결할 때 매우 유용합니다. 데이터 스트리밍 환경에서 실시간으로 가장 큰(또는 작은) K개의 원소를 유지해야 할 때도 힙이 큰 역할을 합니다.

또 다른 힙의 응용으로는 ‘힙 정렬(Heap Sort)‘이 있습니다. 힙 정렬은 힙의 특성을 이용해 리스트를 정렬하는 알고리즘이에요. 모든 원소를 힙에 넣은 후 하나씩 꺼내면 정렬된 순서로 원소를 얻을 수 있죠.

여러분, 이제 힙에 대해 어느 정도 감이 오시나요? 처음에는 조금 복잡해 보일 수 있지만, 실제로 사용해보면 매우 강력하고 유용한 도구라는 것을 느끼실 수 있을 거예요.

힙을 잘 이해하고 활용하면 많은 알고리즘 문제를 효율적으로 해결할 수 있습니다. 예를 들어, 다익스트라 알고리즘이나 프림 알고리즘과 같은 그래프 알고리즘에서도 힙이 중요한 역할을 한답니다.

앞으로 알고리즘 문제를 풀거나 프로그램을 개발할 때 “이 상황에서 힙을 사용할 수 있을까?”라고 한 번씩 생각해보세요. 여러분의 코드가 더욱 효율적이고 강력해질 거예요!

마지막으로, 힙은 단순히 컴퓨터 과학의 이론에 그치지 않고 실제 시스템에서도 널리 사용됩니다. 운영 체제의 작업 스케줄링, 네트워크 라우팅 알고리즘, 데이터 압축 등 다양한 분야에서 힙이 활용되고 있어요.