[자료 구조]이진 힙 Binary Heap

출처 

ChatGPT

---

이진 힙 (Binary Heap)은 완전 이진 트리의 한 형태로, 힙 특성을 만족하는 자료구조이다. 이진 힙은 주로 최소 힙(Min Heap)과 최대 힙(Max Heap) 두 가지 유형으로 나뉜다.

 

최소 힙 Min Heap

부모 노드가 항상 자식 노드보다 작거나 같은 값을 가진다. 따라서 루트 노드에는 트리에서 가장 작은 값이 위치한다.

최대 힙 Max Heap

부모 노드가 항상 자식 노드보다 크거나 같은 값을 가진다. 따라서 루트 노드에는 트리에서 가장 큰 값이 위치한다.

 

1. 이진 힙의 특성

완전 이진 트리 Complete Binary Tree

이진 힙은 완전 이진 트리 구조를 유지해야 한다. 즉, 모든 레벨은 가득 차 있으며, 마지막 레벨은 왼쪽부터 차례대로 노드가 채워져야 한다.

힙 속성 Heap Property

최대 힙에서는 부모 노드가 자식 노드보다 크거나 같아야 하고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같아야 한다. 이 속성이 유지되어야 힙이 올바르게 동작한다.

 

2. 이진 힙의 주요 연산 + 3. 이진 힙의 배열 표현

• 관련 글 -> [자료 구조][Java] 힙 Heap

Heap에 대해 작성한 글의 내용(주요 연산과 배열 표현)은 동일함.

 

4. 이진 힙의 구현 예시 (최소 힙)

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    // 부모 노드의 인덱스
    private int getParentIndex(int index) { return (index - 1) / 2; }
    
    // 왼쪽 자식 노드의 인덱스
    private int getLeftChildIndex(int index) { return 2 * index + 1; }
    
    // 오른쪽 자식 노드의 인덱스
    private int getRightChildIndex(int index) { return 2 * index + 2; }

    // 요소 삽입
    public void insert(int value) {
        if (size == capacity) throw new IllegalStateException("Heap is full");

        heap[size] = value;
        size++;
        heapifyUp(size - 1);  // 삽입 후 힙 업 실행
    }

    // 힙 업(상향식 힙 정렬)
    private void heapifyUp(int index) {
        while (index > 0 && heap[index] < heap[getParentIndex(index)]) {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }

    // 최솟값(루트) 삭제
    public int removeMin() {
        if (size == 0) throw new IllegalStateException("Heap is empty");

        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);  // 삭제 후 힙 다운 실행
        return min;
    }

    // 힙 다운(하향식 힙 정렬)
    private void heapifyDown(int index) {
        int smallest = index;
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }

        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    // 두 요소 교환
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 힙 내용 출력
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(20);
        minHeap.insert(15);
        minHeap.insert(30);
        minHeap.insert(5);
        minHeap.insert(10);

        minHeap.printHeap();  // 출력: 5 10 30 20 15

        System.out.println("Min value removed: " + minHeap.removeMin());  // 출력: 5
        minHeap.printHeap();  // 출력: 10 15 30 20
    }
}

 

5. 이진 힙의 응용

1. 우선순위 큐 Priority Queue

이진 힙은 우선순위 큐를 구현하는 데 많이 사용된다. 우선순위 큐는 FIFO 규칙 대신, 우선순위가 높은 요소가 먼저 처리되는 큐로, 힙을 이용하여 빠르게 삽입 및 삭제 연산을 수행할 수 있다. 자바의 PriorityQueue는 내부적으로 이진 최소 힙을 사용하여 구현된다.

2. 힙 정렬 Heap Sort

힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 배열을 힙으로 변환한 후, 최댓값 또는 최솟값을 하나씩 제거하여 정렬된 배열을 생성한다. 힙 정렬의 시간 복잡도는 O(n log n)이며, 제자리 정렬(in-place sorting)이 가능하다.

• 관련 글 -> [알고리즘] 제자리 정렬 In-Place Sorting

3. 다익스트라 알고리즘 Dijkstra's Algorithm

최단 경로 탐색 알고리즘인 다익스트라 알고리즘에서, 우선순위 큐를 사용하여 가장 작은 거리를 가진 정점을 선택하는 데 이진 힙이 사용ehls다. 이진 힙은 다익스트라 알고리즘의 성능을 크게 향상시킨다.

 

결론

이진 힙(Binary Heap)은 완전 이진 트리 구조를 유지하면서, 최댓값 또는 최솟값을 빠르게 찾고 삽입 및 삭제를 효율적으로 수행할 수 있는 자료구조이다. 이진 힙은 우선순위 큐, 힙 정렬, 최단 경로 탐색 알고리즘 등에서 중요한 역할을 하며, 각 연산은 O(log n) 또는 O(n) 시간 복잡도를 가진다.