힙(Heap)의 개념 및 구현

힙(Heap)의 개념 및 구현

힙(Heap)은 트리 기반의 데이터 구조로, 우선순위 큐(Priority Queue)를 구현하거나 정렬 알고리즘에서 효율적으로 사용할 수 있는 자료구조입니다. 힙은 주로 최대값 또는 최소값을 빠르게 찾기 위한 목적으로 사용됩니다.
이번 포스팅에서는 힙의 개념, 특징, 유형, 구현 방법, 그리고 활용 사례를 살펴보겠습니다.

---

1. 힙의 개념

1.1 힙(Heap)이란?

힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가지며, 다음과 같은 조건을 만족하는 트리입니다:

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

1.2 힙의 특징

• 완전 이진 트리: 힙은 왼쪽에서 오른쪽으로 순서대로 채워진다.
• 힙 속성: 부모-자식 간 관계에서 최소값 또는 최대값이 항상 루트에 위치.
• 효율성: 삽입과 삭제 연산이 O(log⁡n)의 시간 복잡도를 갖는다.

---

2. 힙의 유형

1. 최대 힙 (Max-Heap):
   • 부모 노드가 자식 노드보다 항상 크거나 같음.
   • 루트 노드에 최대값이 저장됨.
2. 최소 힙 (Min-Heap):
   • 부모 노드가 자식 노드보다 항상 작거나 같음.
   • 루트 노드에 최소값이 저장됨.

---

3. 힙의 주요 연산

3.1 삽입 (Insert)

• 새로운 데이터를 힙의 마지막 위치에 삽입.
• 힙 속성 복원: 부모와 자식을 비교하며 적절한 위치로 이동(Heapify-Up).

3.2 삭제 (Delete)

• 루트 노드를 삭제하고 마지막 노드를 루트로 이동.
• 힙 속성 복원: 자식과 비교하며 적절한 위치로 이동(Heapify-Down).

3.3 힙 생성 (Build Heap)

• 배열로 표현된 데이터에서 Heapify를 반복 수행하여 힙을 생성.

---

4. 힙 구현

4.1 배열을 사용한 힙 구현

힙은 배열(Array)로 표현되며, 노드 간 관계는 인덱스를 통해 정의됩니다:

• 부모 노드: index=i
• 왼쪽 자식: 2i+1
• 오른쪽 자식: 2i+2

---

4.2 C#으로 힙 구현

아래는 최소 힙(Min-Heap)의 구현입니다.

using System;
using System.Collections.Generic;

public class MinHeap
{
    private List<int> heap;

    public MinHeap()
    {
        heap = new List<int>();
    }

    // 삽입 연산
    public void Insert(int value)
    {
        heap.Add(value);
        HeapifyUp(heap.Count - 1);
    }

    // 삭제 연산
    public int RemoveMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        int min = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        HeapifyDown(0);
        return min;
    }

    // 최소값 반환
    public int GetMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");
        return heap[0];
    }

    // 힙 위로 재정렬
    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;

            if (heap[index] >= heap[parentIndex])
                break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    // 힙 아래로 재정렬
    private void HeapifyDown(int index)
    {
        int lastIndex = heap.Count - 1;

        while (true)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallest = index;

            if (leftChildIndex <= lastIndex && heap[leftChildIndex] < heap[smallest])
                smallest = leftChildIndex;

            if (rightChildIndex <= lastIndex && heap[rightChildIndex] < heap[smallest])
                smallest = rightChildIndex;

            if (smallest == index)
                break;

            Swap(index, smallest);
            index = smallest;
        }
    }

    // 노드 교환
    private void Swap(int i, int j)
    {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 힙 내용 출력
    public void PrintHeap()
    {
        Console.WriteLine(string.Join(", ", heap));
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        MinHeap minHeap = new MinHeap();

        minHeap.Insert(10);
        minHeap.Insert(5);
        minHeap.Insert(3);
        minHeap.Insert(2);

        Console.WriteLine("Heap after insertions:");
        minHeap.PrintHeap();

        Console.WriteLine($"Minimum value: {minHeap.GetMin()}");

        Console.WriteLine($"Removed minimum: {minHeap.RemoveMin()}");
        minHeap.PrintHeap();
    }
}

---

5. 힙의 활용 사례

5.1 우선순위 큐

• 힙은 우선순위 큐를 효율적으로 구현하는 데 사용됩니다.
• 예: 작업 스케줄링, 네트워크 패킷 처리.

5.2 힙 정렬 (Heap Sort)

• 힙을 사용하여 O(nlog⁡n)시간 복잡도로 정렬을 수행합니다.

5.3 다익스트라 알고리즘

• 그래프 탐색에서 최소 비용 경로를 찾는 알고리즘에 활용됩니다.

5.4 이벤트 시뮬레이션

• 시간이 정렬된 이벤트 처리에서 힙이 유용합니다.

---

6. 힙의 장단점

6.1 장점

• 효율적인 삽입, 삭제 연산 (O(log n))
• 정렬 및 우선순위 처리에 최적화.

6.2 단점

• 배열 크기가 커질수록 메모리 관리가 복잡.
• 완전 이진 트리 구조를 유지해야 하므로 특정 삽입 순서에서 성능 저하 가능.

---

힙은 데이터의 우선순위를 기반으로 효율적으로 관리하고 처리할 수 있는 자료구조로, 다양한 알고리즘에서 중요한 역할을 합니다.