1. 힙이란 무엇인가

자료구조 중 힙(Heap)은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조이다.
반정렬 상태(정렬된 상태가 아니다)이며, 완전이진트리와는 다르게 중복값이 허용된다.

위 사진은 최대힙과 최소힙의 사진인데,
최대힙은 가장 큰 요소가 가장 위에있고,
최소힙은 가장 작은 요소가 가장 위에 위치한다.

(힙 자료구조는 보통 배열을 사용하며, 0번째 인덱스는 계산을 편하게 하기위해 사용하지 않는다. 부모노드의 인덱스가 1이 되어진다.)

1.1 힙의 장단점

장점

빠른 최솟값/최댓값 검색: O(1).
삽입/삭제의 효율성: O(log N).

단점

배열이나 리스트처럼 특정 인덱스에 바로 접근할 수 없음.
순차적 접근이 필요한 경우 성능 저하.

2. 자바에서 힙을 어떻게 구현하는가

Java에서는 PriorityQueue 클래스를 사용하여 힙을 쉽게 구현할 수 있습니다.
기본적으로 PriorityQueue는 최소 힙으로 동작하며, 최대 힙을 구현하려면 Comparator를 사용해야 합니다.

2.1 최소 힙 구현 예제

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // PriorityQueue는 기본적으로 최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 요소 추가
        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(30);
        minHeap.add(1);

        // 힙 상태 출력
        System.out.println("힙 상태: " + minHeap); // [1, 5, 30, 10] (최솟값이 루트에 위치)

        // 최솟값 가져오기
        System.out.println("최솟값: " + minHeap.peek()); // 1

        // 최솟값 제거
        System.out.println("제거된 최솟값: " + minHeap.poll()); // 1
        System.out.println("힙 상태: " + minHeap); // [5, 10, 30]
    }
}

2.2 최대 힙 구현 예제

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.add(10);
        maxHeap.add(5);
        maxHeap.add(30);
        maxHeap.add(1);

        // 힙 상태 출력
        System.out.println("힙 상태: " + maxHeap); // [30, 10, 5, 1] (최댓값이 루트에 위치)

        // 최댓값 가져오기
        System.out.println("최댓값: " + maxHeap.peek()); // 30

        // 최댓값 제거
        System.out.println("제거된 최댓값: " + maxHeap.poll()); // 30
        System.out.println("힙 상태: " + maxHeap); // [10, 1, 5]
    }
}

3. 예시를 통한 설명

3.1 힙의 기본 메서드를 이용한 예시

import java.util.PriorityQueue;

public class HeapMethodsExample {
    public static void main(String[] args) {
        // PriorityQueue 생성 (기본적으로 최소 힙)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 1. add(E e) - 요소 추가
        minHeap.add(15);
        minHeap.add(10);
        minHeap.add(20);

        // 2. offer(E e) - 요소 추가 (실패 시 false 반환)
        minHeap.offer(5);

        // 3. peek() - 루트 요소 확인 (제거하지 않음)
        System.out.println("최솟값 (peek): " + minHeap.peek());

        // 4. poll() - 루트 요소 제거 및 반환
        System.out.println("제거된 값 (poll): " + minHeap.poll());

        // 5. remove(Object o) - 특정 요소 제거
        boolean isRemoved = minHeap.remove(15);
        System.out.println("15 제거 여부: " + isRemoved);

        // 6. size() - 힙의 크기 확인
        System.out.println("힙 크기: " + minHeap.size());

        // 7. isEmpty() - 힙이 비어 있는지 확인
        System.out.println("힙이 비었는가: " + minHeap.isEmpty());

        // 8. clear() - 힙의 모든 요소 제거
        minHeap.clear();
        System.out.println("clear() 후 힙이 비었는가: " + minHeap.isEmpty());

        // 9. contains(Object o) - 특정 요소 포함 여부 확인
        minHeap.add(25);
        minHeap.add(30);
        System.out.println("30 포함 여부: " + minHeap.contains(30));

        // 10. toArray() - 힙의 요소를 배열로 반환
        Object[] array = minHeap.toArray();
        System.out.print("toArray() 결과: ");
        for (Object num : array) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 11. iterator() - 힙 요소를 순회하는 Iterator 반환
        System.out.print("Iterator로 힙 출력: ");
        for (Integer num : minHeap) {
            System.out.print(num + " ");
        }
    }
}

3.2 힙 정렬 예제

import java.util.PriorityQueue;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {10, 5, 30, 1, 25};
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 배열 요소를 힙에 삽입
        for (int num : arr) {
            minHeap.add(num);
        }

        // 힙에서 요소를 꺼내어 정렬
        System.out.println("정렬된 배열:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 1 5 10 25 30
        }
    }
}

minheap이라는 최소 힙을 구현한 후,
for문을 통해서 배열의 모든 요소를 힙에 Add한다.

그리고 while문에 힙이 비어질때까지 순서대로 요소를 Poll한다.

4. 출처

https://hoehen-flug.tistory.com/32
https://go-coding.tistory.com/25