Java에서 Heap 정리

🔹 Heap이란?

Heap은 완전 이진 트리(Complete Binary Tree) 형태의 자료구조로, 항상 루트(root) 노드가 최소값 또는 최대값을 유지하도록 정렬됨.

• 최소 힙(Min Heap): 루트 노드가 가장 작은 값을 가짐.
• 최대 힙(Max Heap): 루트 노드가 가장 큰 값을 가짐.
• 이진 트리 기반으로 동작하며, 삽입/삭제 시 정렬(Heapify)이 자동으로 수행됨.

🔹 Java에서 Heap을 구현하는 방법

Java에서는 PriorityQueue 클래스를 사용하여 Heap을 구현할 수 있음.

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 기본적으로 최소 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // 최대 힙

• PriorityQueue는 기본적으로 최소 힙(Min Heap)으로 동작하며, Comparator를 이용해 정렬 기준을 바꿀 수 있음.
• Comparator.reverseOrder()를 사용하면 최대 힙으로 변환 가능.

🔹 왜 Java에는 Heap<> 클래스를 제공하지 않을까?

1️⃣ Heap은 일반적인 자료구조가 아니라 "우선순위 큐(Priority Queue)"의 한 형태

• Java에서는 Heap을 별도의 자료구조로 제공하는 대신, Heap의 핵심 기능(우선순위 유지)을 PriorityQueue에서 지원함.
• 즉, Java에서 "우선순위 큐"라는 개념이 Heap의 핵심이라고 판단했기 때문.

2️⃣ Heap은 단순한 데이터 구조가 아니라 "정렬이 필요한" 특수한 구조

• 일반적인 Queue는 FIFO(선입선출) 방식이라 간단하게 제공할 수 있음.
• 하지만 Heap은 삽입/삭제할 때마다 재정렬(Heapify)이 필요하여 복잡한 로직이 요구됨.
• Java에서는 일반적인 자료구조는 인터페이스로 제공하지만, Heap처럼 특정한 정렬이 필요한 구조는 PriorityQueue 같은 클래스를 활용하게 설계함.

3️⃣ Heap은 다양한 용도로 사용되기 때문에 일반적인 Heap<> 클래스를 만들기 어려움

• Heap은 최소 힙과 최대 힙이 있고, 경우에 따라 정렬 기준이 달라짐.
• Heap<> 클래스를 만들려면 모든 경우를 다 포함해야 하므로 비효율적.
• 대신 Comparator를 활용하여 정렬 기준을 변경할 수 있는 PriorityQueue가 더 유연한 방법.

📢 결론: Java는 Heap을 별도로 제공하지 않고 PriorityQueue를 활용하도록 설계했으며, 이는 더 유연하고 효율적인 방식임.

🔹 Heap에서 Comparator를 활용하는 방법

PriorityQueue<Integer> absMinHeap = new PriorityQueue<>(
    Comparator.comparingInt((Integer x) -> Math.abs(x)) // 절댓값 기준 정렬
              .thenComparingInt(x -> x) // 절댓값이 같으면 원래 숫자 기준 정렬
);

• comparingInt(x -> Math.abs(x)) → 절댓값 기준 정렬
• thenComparingInt(x -> x) → 절댓값이 같으면 원래 숫자 기준으로 정렬

Comparator.comparingInt()와 제네릭의 문제

Comparator.comparingInt(x -> Math.abs(x))는 Integer 타입에 대해 자동 추론되므로 를 명시하지 않으면 에러 발생 가능.

Java의 Comparator.comparingInt()는 내부적으로 int를 기대하기 때문에, 제네릭을 정확히 설정해야 한다.

✔ 정상 코드

PriorityQueue<Integer> heap = new PriorityQueue<>(
    Comparator.<Integer>comparingInt(x -> Math.abs(x)).thenComparingInt(x -> x)
);

✔ 에러 발생 코드

PriorityQueue<int> heap = new PriorityQueue<>( // ❌ int는 제네릭 불가!
    Comparator.comparingInt(x -> Math.abs(x)).thenComparingInt(x -> x)
);

➡ PriorityQueue는 사용할 수 없고, 항상 PriorityQueue를 사용해야 함.

🔹 Heap의 주요 메서드

• 삽입: add(E e), offer(E e) → 요소 추가
• 삭제: poll() → 루트(최소/최대값) 제거 후 반환
• 조회: peek() → 루트 요소 조회(삭제하지 않음)

✅ 최종 정리

1️⃣ Heap은 우선순위를 유지하는 자료구조이며, Java에서는 이를 PriorityQueue로 지원함.
2️⃣ Heap을 별도의 Heap<> 클래스로 제공하지 않는 이유는 다음과 같음:

• 우선순위 큐(Priority Queue) 개념이 Heap의 핵심이기 때문
• Heap은 단순한 구조가 아니므로 별도의 클래스보다 PriorityQueue가 더 적합
• Comparator를 활용하면 다양한 정렬 기준을 쉽게 설정할 수 있음
  3️⃣ Java에서 Heap을 사용하려면 PriorityQueue를 활용하면 된다! 🚀