자료구조 - Heap

힙(Heap)이란?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 설계된 완전 이진트리를 기본으로 한 자료구조 입니다.

완전 이진트리란?

완전 이진 트리는 각 노드가 최대 2개의 자식 노드를 가지는 트리로, 최하단 레벨의 노드는 좌측부터 차례로 채워지며, 마지막 레벨을 제외한 모든 노드가 완전히 채워져 있어야 합니다. 노드 삽입은 항상 최하단 좌측부터 이루어집니다.

특징

• 완전 이진트리
• 중복값 허용
• 최댓값, 최솟값을 빠르게 찾기 용이
• 종류
  • 최대 힙(max heap): 루트 값이 최댓값, 부모 노드 값 >= 자식 노드 값
  • 최소 힙(min heap): 루트 값이 최솟값, 부모 노드 값 <= 자식 노드 값
    
    

시간복잡도

삽입, 삭제 연산: O(logn)

힙 구현 코드 (힙 정렬)

힙 정렬을 통해 최대 힙을 구성한 뒤, 최대 값을 추출하고 힙 크기를 줄여가며 반복하는 방식으로 정렬을 수행합니다.

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};

        // 최대 힙 구성  -> [9, 7, 5, 1, 2]
        buildMaxHeap(arr);

        // 최댓값 추출  -> 9
        int max = extractMax(arr);
        System.out.println("최댓값: " + max); 

        // 최댓값 제거 후 배열의 상태를 출력  -> [7, 2, 5, 1]
        System.out.println("최댓값 제거 후 배열: " + Arrays.toString(Arrays.copyOf(arr, arr.length - 1))); 
    }

    // 최대 힙 구성  
    public static void buildMaxHeap(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    // 힙 속성을 유지하도록 재구성
    private static 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) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    // 배열의 두 요소를 교환
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 힙에서 최댓값을 추출하고 제거
    public static int extractMax(int[] arr) {
        if (arr.length == 0)
            throw new IllegalStateException("Heap is empty.");

        int max = arr[0];

        // 마지막 요소를 루트로 이동
        arr[0] = arr[arr.length - 1];

        // 배열의 크기를 줄임
        int n = arr.length - 1;

        // 힙 속성을 유지하기 위해 재정렬
        heapify(arr, n, 0);

        return max;
    }
}

힙 응용

우선순위 큐

힙의 속성을 이용하여 우선순위 큐를 구현할 수 있습니다.

• 우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조입니다.
• Java에서는 PriorityQueue 클래스를 사용하여 우선순위 큐를 구현할 수 있습니다.
• 기본적으로 PriorityQueue는 최소 힙으로 구현되어 있어, 가장 작은 값을 가진 요소가 먼저 제거됩니다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(3);
pq.offer(1);
pq.offer(2);

System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 2
System.out.println(pq.poll()); // 3

만약 최대 힙으로 구현하고 싶다면, Collections.reverseOrder()를 사용하여 우선순위를 역순으로 지정할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

---

ref.
https://heytech.tistory.com/105