힙 (Heap)

힙이란?

힙(heap)은 데이터를 저장하고 관리하는 자료구조 중 하나로,
최대값이나 최소값을 빠르게 찾기 위한 목적으로 사용된다.

힙은 '부모값이 자식값보다 항상 크다'라는 조건을 만족하는 완전 이진 트리를 말한다.
완전이진트리는 트리의 한 종류이다. 완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전'이라는 말은 '부모는 자식을 왼쪽부터 추가하는 모양을 유지한다'는 뜻이고, '이진'이라는 말은 '부모가 가질 수 있는 자식의 개수는 최대 2개이다'라는 뜻이다.

자바에서는 java.util 패키지의 PriorityQueue 클래스를 사용하여 힙을 구현할 수 있다. PriorityQueue 클래스는 내부적으로 힙 구조를 사용하여 요소를 저장하며, add() 메서드를 통해 요소를 추가하고, poll() 메서드를 통해 최댓값 또는 최솟값을 반환하고 제거할 수 있다.

예를 들어, 다음은 정수형 값을 저장하는 최대 힙을 구현하는 예시 코드이다.

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

public class MaxValue {
    public static void main(String[] args) {
        // 방법 1
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(5);
        maxHeap.add(3);
        maxHeap.add(9);
        maxHeap.add(1);
        maxHeap.add(7);
        System.out.println(maxHeap.peek()); // 9

        // 방법 2
        int[] arr = {5, 3, 9, 1, 7};
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : arr) {
            heap.add(num);
        }
        System.out.println(heap.peek()); // 9

        // 방법 3 (일반for문 사용)
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        System.out.println(max); // 9
    }
}

이 코드에서는 PriorityQueue 클래스의 생성자에 Collections.reverseOrder()를 전달하여 최대 힙을 생성한다. add() 메서드를 사용하여 5,3,9,1,7을 순서대로 추가하고, peek()메소드를 사용하여 최대값이 무엇인지 출력한다. 만약 peek()메소드 대신에 poll() 메소드를 사용하면 최대값을 반환하고 제거까지 한다.