Heap

---

Heap 자료구조는 완전 이진 트리를 기반으로 하며, 최댓값 또는 최솟값을 빠르게 찾기 위한 구조다.

Heap은 크게 MinHeap과 MaxHeap으로 나뉜다.

🧩 MinHeap

정의

MinHeap은 부모 노드가 자식 노드보다 항상 작거나 같은 완전 이진 트리다.

루트 노드에 가장 작은 값이 위치하므로 최솟값 조회가 빠르다.

삽입 과정

1. 새로운 값을 맨 마지막 노드에 추가한다.
2. 부모보다 작으면 swap 한다.
3. 부모보다 작지 않을 때까지 반복한다.

삭제 과정

1. 루트 노드를 제거한다.
2. 마지막 노드를 루트로 옮긴다.
3. 자식 노드와 비교하며 내려가면서 정렬한다.

🧩 MaxHeap

정의

MaxHeap은 부모 노드가 자식 노드보다 항상 크거나 같은 완전 이진 트리다.

루트 노드에 가장 큰 값이 위치하므로 최댓값 조회가 빠르다.

삽입 과정

1. 새로운 값을 맨 마지막 노드에 추가한다.
2. 부모보다 크면 swap 한다.
3. 부모보다 크지 않을 때까지 반복한다.

삭제 과정

1. 루트 노드를 제거한다.
2. 마지막 노드를 루트로 옮긴다.
3. 자식 노드와 비교하며 내려가면서 정렬한다.

🧪 Java 샘플 코드

MinHeap 예시

import java.util.PriorityQueue;

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

        minHeap.offer(5);
        minHeap.offer(3);
        minHeap.offer(8);
        minHeap.offer(1);

        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }
    }
}

MaxHeap 예시

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

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

        maxHeap.offer(5);
        maxHeap.offer(3);
        maxHeap.offer(8);
        maxHeap.offer(1);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

⚠️ 주의사항

• Heap은 정렬된 구조가 아니라 우선순위가 빠르게 유지되는 구조다.
• 모든 탐색이 빠른 것은 아니고, 최댓값 또는 최솟값 접근이 핵심이다.

연결문서