30초 답변

Heap은 부모가 자식보다 작거나 큰 성질을 유지하는 완전 이진 트리입니다. 최소 힙에서는 최솟값을 O(1)에 확인하고 삽입과 삭제를 O(log n)에 처리할 수 있습니다. Priority Queue는 작업 스케줄링, 다익스트라, top K 문제에 자주 쓰입니다.

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

1

2

3

4

5

Heap에서 최솟값 조회가 O(1)인 이유는 무엇인가요?

최소 힙에서는 heap property에 따라 root가 항상 가장 작은 값이기 때문입니다.

이전 질문다음 꼬리질문

부가 설명

일반 Queue는 먼저 들어온 순서가 중요하지만, 어떤 문제에서는 “가장 작은 거리”, “가장 높은 우선순위”가 먼저 나와야 합니다. 이때 Priority Queue를 사용합니다. 배열로 매번 정렬하면 비용이 커지기 때문에 heap처럼 필요한 순서만 부분적으로 유지하는 구조가 유용합니다.

Heap은 전체가 정렬된 자료구조가 아닙니다. 부모와 자식 사이의 우선순위 관계만 유지하므로 root에는 최소 또는 최대가 빠르게 올라옵니다. 이 차이를 이해해야 heap 배열을 봤을 때 왜 전체 순서가 정렬되어 있지 않은지 헷갈리지 않습니다.

한 줄 정리

Heap은 전체 정렬 대신 root 우선순위를 빠르게 유지해 Priority Queue를 실용적으로 만듭니다.