[자료구조] 힙(Heap)

힙(Heap)이란?

• 정의: 힙은 완전 이진 트리의 일종으로, 우선순위 큐(Priority Queue)를 구현하는 데 자주 사용되는 구조이다.
• 특징
  - 힙 속성(Heap Property)을 만족한다.
     - 최대 힙(Max-Heap): 부모 노드의 값이 항상 자식 노드보다 크거나 같다.
     - 최소 힙(Min-Heap): 부모 노드의 값이 항상 자식 노드보다 작거나 같다.
  - 완전 이진 트리 형태를 유지한다.
• 장단점
  - 장점
     - 효율적인 삽입 및 삭제 연산
     - 최댓값 또는 최솟값을 빠르게 찾을 수 있음
  - 단점
     - 트리의 균형을 유지해야 하므로 구현 복잡성이 있음
     - 배열 기반 구현에서는 추가 메모리 사용 가능

---

힙의 종류

• 최대 힙(Max-Heap): 가장 큰 값이 루트 노드에 위치
• 최소 힙(Min-Heap): 가장 작은 값이 루트 노드에 위치

---

힙의 주요 연산

• 삽입(Insert)
  - 데이터를 힙에 추가한 뒤, 힙 속성을 유지하기 위해 재정렬
  - 시간 복잡도: O(log n)
• 삭제(Delete)
  - 루트 노드를 제거한 뒤, 마지막 노드를 루트로 이동하고 재정렬
  - 시간 복잡도: O(log n)
• 최댓값/최솟값 조회
  - 최대 힙: 루트 노드가 최댓값
  - 최소 힙: 루트 노드가 최솟값
  - 시간 복잡도: O(1)

---

힙의 구현

자바에서는 PriorityQueue 클래스를 사용하여 힙을 구현할 수 있다.

 

최소 힙 구현 예제

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.offer(10);
        minHeap.offer(5);
        minHeap.offer(20);
        
        System.out.println("Min element: " + minHeap.peek()); // 출력: 5
        System.out.println("Remove element: " + minHeap.poll()); // 출력: 5
        System.out.println("Min element: " + minHeap.peek()); // 출력: 10

 

 

최대 힙 구현 예제

자바의 PriorityQueue는 기본적으로 최소 힙을 제공하므로, 최대 힙은 Comparator를 사용하여 구현한다.

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        maxHeap.offer(10);
        maxHeap.offer(5);
        maxHeap.offer(20);
        
        System.out.println("Max element: " + maxHeap.peek()); // 출력: 20
        System.out.println("Remove element: " + maxHeap.poll()); // 출력: 20
        System.out.println("Max element: " + maxHeap.peek()); // 출력: 10
    }
}

---

힙의 시간 복잡도

연산	설명	시간 복잡도
삽입	데이터를 추가하고 정렬	O(log n)
삭제	루트 노드를 제거하고 정렬	O(log n)
최댓값/최솟값	루트 노드 확인	O(1)

---

힙의 활용 예시

• 우선순위 큐(Priority Queue)
  : 작업 스케줄링, 네트워크 패킷 처리 등 우선순위가 중요한 작업에 사용
• 최대/최소 k개 원소 찾기
  : 배열에서 가장 큰 k개 원소 또는 가장 작은 k개 원소를 빠르게 찾을 때 사용
• 힙 정렬(Heap Sort)
  : 힙을 사용하여 정렬
• 다익스트라 알고리즘
  : 그래프에서 최단 경로를 찾을 때 사용

---

힙 정렬(Heap Sort)

• 정의: 힙을 사용하여 데이터를 정렬하는 알고리즘
• 특징
  - 불안정 정렬(Unstable Sort)
  - 최대 힙을 사용하여 내림차순 정렬, 최소 힙을 사용하여 오름차순 정렬
• 시간 복잡도
  - 빌드 힙(Build Heap): O(n)
  - 정렬 과정: O(n log n)
• 예제

public void heapSort(int[] arr) {
    int n = arr.length;

    // 빌드 최대 힙
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 힙 정렬
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}