1Page 노트정리 힙

May 25, 2024

1 Page 노트 정리

new repo

힙 (Heap)

힙(Heap) 은 완전 이진 트리(Complete Binary Tree) 형태를 가진 자료구조로, 각 노드가 특정 순서를 유지하도록 구성됩니다. 힙은 주로 최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지로 구분됩니다.

종류

최대 힙 (Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 힙입니다. 루트 노드는 가장 큰 값을 가집니다.
최소 힙 (Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 힙입니다. 루트 노드는 가장 작은 값을 가집니다.

힙의 성질

완전 이진 트리: 모든 레벨이 꽉 차 있거나, 마지막 레벨의 노드가 왼쪽부터 채워지는 이진 트리.
힙 속성:
- 최대 힙: 부모 노드의 값 ≥ 자식 노드의 값
- 최소 힙: 부모 노드의 값 ≤ 자식 노드의 값

주요 연산

삽입 (Insert): 새로운 요소를 힙에 추가하는 연산.
삭제 (Delete/Extract): 루트 노드를 삭제하는 연산.
힙 구성 (Heapify): 주어진 배열을 힙으로 구성하는 연산.
힙 정렬 (Heap Sort): 힙을 이용해 배열을 정렬하는 연산.

시간 복잡도

연산	시간 복잡도
삽입 (Insert)	O(log n)
삭제 (Delete)	O(log n)
힙 구성 (Heapify)	O(n)
힙 정렬 (Heap Sort)	O(n log n)

힙(Heap)의 주요 연산과 시간 복잡도가 저렇게 나오는 이유

1. 삽입 (Insert)

시간 복잡도: O(log n)
이유: 힙에 새로운 요소를 삽입할 때, 먼저 완전 이진 트리의 가장 마지막 위치에 요소를 추가합니다. 그 후, 힙 속성을 유지하기 위해 요소를 상향식으로 비교하며 부모 노드와 교환합니다(이 과정을 힙화 또는 heapify라고 합니다). 완전 이진 트리의 높이는 log(n)이므로, 최악의 경우 요소가 루트까지 이동하는 데 걸리는 시간은 O(log n)입니다.

2. 삭제 (Delete/Extract)

시간 복잡도: O(log n)
이유: 힙에서 삭제 연산은 보통 루트 노드(최대 힙의 경우 최대값, 최소 힙의 경우 최소값)를 삭제합니다. 루트 노드를 삭제한 후, 트리의 가장 마지막 노드를 루트 위치로 옮기고, 힙 속성을 유지하기 위해 이 노드를 하향식으로 비교하며 자식 노드와 교환합니다(이 과정을 힙화 또는 heapify라고 합니다). 마찬가지로, 완전 이진 트리의 높이는 log(n)이므로, 최악의 경우 노드가 리프 노드까지 이동하는 데 걸리는 시간은 O(log n)입니다.

3. 힙 구성 (Heapify)

시간 복잡도: O(n)
이유: 배열을 힙으로 변환하는 작업을 힙 구성 또는 힙 빌딩이라고 합니다. 주어진 배열을 힙으로 변환할 때, 배열의 중간부터 시작하여 역순으로 각 요소에 대해 heapify를 호출합니다. 배열의 절반은 리프 노드이므로 이들은 이미 힙 속성을 만족합니다. 나머지 요소에 대해 heapify를 호출할 때, 각 heapify 호출의 평균 시간 복잡도는 O(1)입니다. 이를 전체 요소에 대해 수행하면 총 시간 복잡도는 O(n)입니다. 이를 증명하는 방법으로는 아마르테 연산(Amortized Analysis)을 이용할 수 있습니다.

4. 힙 정렬 (Heap Sort)

시간 복잡도: O(n log n)
이유: 힙 정렬은 두 단계로 이루어집니다:
1. 힙 구성(Heapify): 주어진 배열을 힙으로 변환하는 작업으로, 시간 복잡도는 O(n)입니다.
2. 정렬(Sort): 힙에서 가장 큰 요소(최대 힙의 경우)를 루트에서 제거하고, 힙 속성을 유지하도록 힙을 재구성하는 작업을 반복합니다. 힙에서 요소를 제거하는 작업은 O(log n)의 시간 복잡도를 가지며, 이를 n번 반복하므로 O(n log n)의 시간 복잡도가 됩니다.

따라서 힙 정렬의 전체 시간 복잡도는 O(n) + O(n log n) = O(n log n)입니다.

힙의 주요 연산과 시간 복잡도 요약

연산	시간 복잡도	설명
삽입 (Insert)	O(log n)	요소를 추가한 후, 상향식으로 힙 속성 유지 (최대 log n 레벨 이동).
삭제 (Delete)	O(log n)	루트 노드를 제거한 후, 하향식으로 힙 속성 유지 (최대 log n 레벨 이동).
힙 구성 (Heapify)	O(n)	배열의 중간부터 시작하여 각 요소에 대해 heapify 호출. Amortized Analysis에 의해 O(n).
힙 정렬 (Heap Sort)	O(n log n)	힙 구성 O(n) + 요소 제거 및 힙 속성 유지 O(n log n).

힙의 구조적 특성(완전 이진 트리)과 각 연산의 동작 방식이 이와 같은 시간 복잡도를 도출하게 합니다.

힙의 구현

최대 힙 (Max Heap) 구현 예제 (Java)

import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대 힙을 구현하기 위해 우선순위 큐를 사용 (내림차순 정렬)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y) -> y - x);

        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);

        // 루트 노드 (최대 값) 출력
        System.out.println(maxHeap.peek());  // 20 출력

        // 루트 노드 제거
        maxHeap.poll();
        System.out.println(maxHeap.peek());  // 10 출력
    }
}

최소 힙 (Min Heap) 구현 예제 (Java)

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // 최소 힙을 구현하기 위해 우선순위 큐를 사용 (기본 정렬: 오름차순)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);

        // 루트 노드 (최소 값) 출력
        System.out.println(minHeap.peek());  // 5 출력

        // 루트 노드 제거
        minHeap.poll();
        System.out.println(minHeap.peek());  // 10 출력
    }
}

힙의 활용

우선순위 큐: 우선순위 큐는 힙을 사용하여 구현됩니다. 각 요소는 우선순위를 가지며, 힙 구조를 통해 높은 우선순위 요소가 먼저 처리됩니다.
힙 정렬: 힙 정렬은 힙을 이용하여 배열을 정렬하는 알고리즘으로, 시간 복잡도가 O(n log n)입니다.
그래프 알고리즘: 다익스트라 알고리즘과 프림 알고리즘 등에서 최소 힙을 사용하여 최단 경로와 최소 스패닝 트리를 찾습니다.

힙은 효율적인 삽입, 삭제 연산을 통해 우선순위 큐와 같은 자료구조를 구현하는 데 유용하며, 다양한 알고리즘의 기반이 되는 중요한 자료구조입니다.