힙 마스터하기: 데이터 구조와 알고리즘 깊이 탐구

Source: Dev.to

소개

힙은 컴퓨터 과학에서 기본적인 자료 구조로, 우선순위 큐를 구현하거나 알고리즘을 최적화하는 데 흔히 사용됩니다. 이 글에서는 힙의 구조, 연산, 그리고 활용 사례를 자세히 살펴봅니다.

힙 종류

힙은 힙 속성을 만족하는 특수한 트리 기반 자료 구조입니다. 주요 유형은 두 가지입니다:

• Min‑heap – 각 부모 노드가 자식 노드보다 작거나 같습니다.
• Max‑heap – 각 부모 노드가 자식 노드보다 크거나 같습니다.

힙 연산

삽입

힙에 요소를 삽입하려면, 먼저 요소를 가장 아래 레벨에 놓고 부모와 비교하면서 필요할 경우 교환하여 힙 속성이 회복될 때까지 “버블 업”합니다.

def insert(heap, value):
    heap.append(value)
    index = len(heap) - 1
    while index > 0:
        parent_index = (index - 1) // 2
        if heap[parent_index] > heap[index]:
            heap[parent_index], heap[index] = heap[index], heap[parent_index]
            index = parent_index
        else:
            break

삭제

요소를 삭제할 때 일반적인 작업은 루트 노드를 제거하는 것입니다. 루트를 힙의 마지막 요소로 교체한 뒤, 힙 속성을 유지하기 위해 “힙화”(버블 다운)합니다.

def delete_root(heap):
    root = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    index = 0
    while True:
        left_child = 2 * index + 1
        right_child = 2 * index + 2
        if left_child < len(heap) and heap[left_child] < heap[index]:
            heap[left_child], heap[index] = heap[index], heap[left_child]
            index = left_child
        elif right_child < len(heap) and heap[right_child] < heap[index]:
            heap[right_child], heap[index] = heap[index], heap[right_child]
            index = right_child
        else:
            break

활용 사례

힙은 다양한 알고리즘과 자료 구조에서 널리 사용됩니다. 대표적인 예로 다익스트라 최단 경로 알고리즘이 있는데, 여기서는 최소 힙을 이용해 가장 작은 임시 거리를 가진 노드를 효율적으로 추출합니다.

결론

힙은 알고리즘 최적화에 중요한 역할을 하는 강력한 자료 구조입니다. 힙 연산을 숙달하면 문제 해결 능력이 향상되고 복잡한 계산 과제를 손쉽게 다룰 수 있게 됩니다.