(코테) [Java] Heap

Heap (힙) - 우선순위가 있는 트리형 자료구조

 

개념 요약

• 힙은 완전 이진 트리 기반의 우선순위 큐
• Min Heap: 부모가 자식보다 항상 작다 → 작은 값이 먼저 나옴
• Max Heap: 부모가 자식보다 항상 크다 → 큰 값이 먼저 나옴
• 대표적 연산:
  • insert / offer()
  • poll() → 가장 우선순위 높은 원소 제거 및 반환
  • peek() → 제거 없이 가장 우선 원소 확인

 

구조 그림 (Min Heap)

       1
     /   \\
    3     5
   / \\   / \\
  8  10  7  9

• 삽입/삭제 시 자동 정렬되도록 구조 유지됨

 

Java 코드 예시

최소 힙 (Min Heap)

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.offer(4);
        minHeap.offer(1);
        minHeap.offer(7);

        System.out.println(minHeap.poll());  // 1
        System.out.println(minHeap.poll());  // 4
    }
}

 

최대 힙 (Max Heap)

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

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.offer(4);
        maxHeap.offer(1);
        maxHeap.offer(7);

        System.out.println(maxHeap.poll());  // 7
        System.out.println(maxHeap.poll());  // 4
    }
}

 

힙 활용 예시

• 다익스트라 알고리즘
• 우선순위가 있는 작업 스케줄링
• K번째 최소/최대값 찾기
• Median 문제 해결 (중앙값 힙)

 

구조	Java 클래스	특징
Min Heap	PriorityQueue<>()	기본 정렬: 오름차순
Max Heap	PriorityQueue<>(Collections.reverseOrder()) PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);	내림차순 우선순위 부여

이렇게 안에 () 조건을 더 걸어줄 수도 있음!

배열에 대해서 [1]번째 배열 값 비교도 가능하니 여러 방식으로 활용하는 눈을 키워보기!