[Java] Java에서의 Heap과 Priority Queue(for Algorithm Guide)

목차

• Heap이란?
• Priority Queue란?
  • 패키지
  • 선언 예제
• 주요 연산
  • offer(element) / add(element)
  • peek()
  • poll()
• 최대 힙(Max-Heap) 구현
  • 1. Comparator.reverseOrder() 또는 람다를 이용한 방법
  • 1. 네거티브 트릭 (Numeric 데이터에 한정)
• 복합 데이터의 정렬과 Comparator 구현

---

Heap이란?

완전 이진 트리(Complete Binary Tree) 형태의 자료구조로, 각 노드가 특정한 순서 조건을 만족한다.

<aside> 💡

완전 이진 트리 구조란?

모든 레벨이 완전히 채워지며, 마지막 레벨은 왼쪽부터 순서대로 채워지는 구조

</aside>

정렬 조건

• 최소 힙: 모든 부모 노드의 값 ≤ 자식 노드의 값
• 최대 힙: 모든 부모 노드의 값 ≥ 자식 노드의 값

주요 특징 및 시간복잡

• 삽입 및 삭제: O(log n)
• 최솟값/최댓값 접근: O(1)

사용 예

자바의 PriorityQueue는 내부적으로 힙 자료구조를 사용하여, 우선순위에 따라 요소들을 효율적으로 관리합니다.

---

Priority Queue란?

내부적으로 힙(Heap)을 사용해 우선순위에 따라 요소들을 관리하는 자료구조

기본적으로 최소 힙(Min-Heap)으로 동작하며, Comparator를 지정해 최대 힙을 구현할 수 있다.

패키지

import java.util.PriorityQueue;

선언 예제

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
    }
}

---

주요 연산

offer(element) / add(element)

새 요소를 최소 힙에 삽입한다.

• 시간복잡도 : $O(logN)$
• 반환타입 : boolean (작업 성공 시 true)

        pq.add(20);                     // [20]
        pq.offer(5);                    // [5, 20]
        System.out.println(pq.add(15)); // [5, 15, 20], 출력: true

<aside> 💡

add는 offer를 호출한다.

    public boolean add(E e) {
        return offer(e);
    }

</aside>

peek()

우선순위가 가장 높은(최소값) 요소를 반환

• 시간복잡도: $O(1)$
• 반환타입: 해당 요소 (큐가 비어 있으면 null)

        System.out.println(pq.peek());  // 출력: 5

poll()

우선순위가 가장 높은 요소를 제거하고 반환

• 시간복잡도: $O(log n)$
• 반환타입: 제거된 요소 (큐가 비어 있으면 null)

        System.out.println(pq.peek());  // 출력: 5
        pq.poll();                      // 5 제거
        System.out.println(pq);         // 출력:[15, 20]
        System.out.println(pq.poll());  // [20], 출력: 15

---

최대 힙(Max-Heap) 구현

자바의 PriorityQueue는 기본적으로 최소 힙(min-heap)으로 동작합니다.

최대 힙을 사용하기 위한 두 가지 방법을 소개합니다.

1. Comparator.reverseOrder() 또는 람다를 이용한 방법

**Comparator.reverseOrder()**또는 람다 표현식을 사용하여 내림차순 정렬 규칙을 적용하면 기본 동작이 최대 힙처럼 동작하게 됩니다.

이 방법은 코드가 깔끔하고, 문자열과 같이 Comparable을 구현한 타입에도 바로 적용할 수 있습니다.

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(10); // [10]
        maxHeap.offer(5);  // [10, 5]
        maxHeap.offer(20); // [20, 5, 10]
        maxHeap.offer(15); // [20, 15, 10, 5]
        System.out.println(maxHeap); // 출력 : [20, 15, 10, 5]
        
        // 문자열에 대한 최대힙은 역사전순 정렬
        PriorityQueue<String> stringMaxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        stringMaxHeap.offer("apple");
        stringMaxHeap.offer("banana");
        stringMaxHeap.offer("cherry");
        stringMaxHeap.offer("date");
        System.out.println(stringMaxHeap); // 출력 : [date, cherry, banana, apple]

2. 네거티브 트릭 (Numeric 데이터에 한정)

PriorityQueue가 최소 힙으로 동작하므로, 입력값에 -1을 곱해 저장하고, 꺼낼 때 다시 -1을 곱하면 최대 힙처럼 사용할 수 있습니다.

        PriorityQueue<Integer> simpleMaxHeap = new PriorityQueue<>();
        simpleMaxHeap.offer(-10);
        simpleMaxHeap.offer(-5);
        simpleMaxHeap.offer(-20);
        simpleMaxHeap.offer(-15);
        System.out.println(simpleMaxHeap);  // 출력 : [-20, -15, -10, -5]

        // poll() 할 때 -1을 곱해 원래 값을 복원하여 최대 힙처럼 동작
        while (!simpleMaxHeap.isEmpty()) {
            int originalValue = -simpleMaxHeap.poll();
            System.out.println(originalValue);
        }

<aside> ⚠️

이 방법은 구현이 단순하나, 가독성이 떨어지고 입력 값이 음수일 경우 추가 처리, 객체에 대한 범용성이 떨어져 권장하지 않습니다.

</aside>

---

복합 데이터의 정렬과 Comparator 구현

PriorityQueue에 저장되는 요소가 배열, 리스트 또는 사용자 정의 클래스와 같이 여러 값을 가진 복합 데이터인 경우, 해당 타입이 Comparable 인터페이스를 구현하지 않으면 자연 정렬이 적용되지 않습니다.

정렬 기준(ex: 두 번째 요소를 기준으로 오름차순)을 지정하기 위해서는 Comparator를 반드시 구현해야 합니다.

2번째 요소를 기준으로 최소 힙, 만약 동일할 경우 1번째 요소를 기준으로 최대 힙을 구현할 경우 다음과 같이 구현할 수 있습니다.

        PriorityQueue<int[]> customComposite = new PriorityQueue<>((a, b) -> {
            if (a[1] == b[1]) return Integer.compare(b[0], a[0]);
            return Integer.compare(a[1], b[1]);
        });
        customComposite.offer(new int[]{3, 100});  // [[3, 100]]
        customComposite.offer(new int[]{1, 20});   // [[1, 20], [3, 100]]
        customComposite.offer(new int[]{3, 20});   // [[3, 20], [3, 100], [1, 20]]
        customComposite.offer(new int[]{2, 30});   // [[3, 20], [2, 30], [1, 20], [3, 100]]
        customComposite.offer(new int[]{5, 20});   // [[5, 20], [3, 20], [1, 20], [3, 100], [2, 30]]