[java] 최대힙, 최소힙

다이어그램으로 힙 sort에 대해 확인하고자 한다면 아래 링크를 클릭해서 참고하면 좋다.
heap sort

시간 복잡도

작업 시간 복잡도:

삽입: 𝑂(log𝑛) — 힙의 말단에 삽입한 후, 정렬 수행.
삭제: 𝑂(log𝑛) — 최상단(root) 노드를 제거한 후, 힙을 재정렬.
접근(최상단 요소 확인): 𝑂(1)

구조

힙 자료구조:

내부적으로 완전 이진 트리(Complete Binary Tree) 구조를 배열로 표현하여 구현된다.
노드 간의 부모-자식 관계는 우선순위에 따라 정렬한다.
최소 힙: 부모 노드는 항상 자식 노드보다 작거나 같다.
최대 힙: 부모 노드는 항상 자식 노드보다 크거나 같다.

최소힙

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

최대힙

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer num1, Integer num2) {
            return -Integer.compare(num1, num2);
        }
    });

Comparator를 사용하여 최대 힙 생성:

Comparator를 구현하여 PriorityQueue의 정렬 기준을 커스터마이징할 수 있다.
Integer.compare(o1, o2)는 o1이 o2보다 작으면 음수, 크면 양수를 반환한다.
-Integer.compare(o1, o2)를 사용하면 기본 정렬 순서를 반대로 뒤집어 내림차순 정렬(최대 힙)을 구현할 수 있다.

참고) 최대 힙 람다식으로 구현

import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대 힙 생성
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

        // 데이터 추가
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);

        // 최대값 제거 및 출력
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());  // 출력: 20, 10, 5
        }
    }
}