힙 / 우선순위 큐 시각화
최소힙·최대힙의 삽입·추출·Heapify를 트리+배열 이중 뷰로 학습하는 인터랙티브 도구
자료구조★★☆
속도
1 / 1크기: 0유효: ✓
힙 유형
연산
현재교환 중비교 중완료
배열 ↔ 트리 인덱스 매핑
부모: parent(i) = floor((i-1)/2)
왼쪽 자식: left(i) = 2i + 1
오른쪽 자식: right(i) = 2i + 2
힙의 구조적 속성과 힙 속성이 어떻게 유지되는지 관찰하세요.
값을 입력하고 실행을 눌러 시작하세요.
힙(Heap)이란?
힙은 완전 이진 트리 기반의 자료구조로, 부모 노드가 항상 자식보다 크거나(최대힙) 작은(최소힙) 속성을 가집니다. 배열로 효율적으로 구현할 수 있으며, 우선순위 큐의 핵심 구현체입니다.
사용 방법
- 1Min/Max Heap을 선택한 후 삽입·추출·Heapify 연산을 실행하세요
- 2트리 뷰와 배열 뷰에서 동일한 데이터가 어떻게 표현되는지 비교하세요
- 3배열 인덱스와 트리 위치의 매핑 공식을 확인하세요
- 4Heapify는 정렬되지 않은 배열을 O(n)에 힙으로 변환합니다
학습 팁
- •삽입: 배열 끝에 추가 → Bubble Up (부모와 비교하며 올라감)
- •추출: 루트 제거 → 마지막을 루트로 → Bubble Down
- •Heapify는 리프가 아닌 내부 노드만 처리하여 O(n)에 완성됩니다
- •우선순위 큐, 힙 정렬, 다익스트라 알고리즘에서 핵심적으로 사용됩니다
자주 묻는 질문
Q. 힙과 BST의 차이?
A. 힙: 부모≥자식(Max) 또는 부모≤자식(Min), O(1) 최대/최소 조회. BST: 왼쪽<부모<오른쪽, O(log n) 임의 값 탐색.
Q. 왜 배열로 구현하나요?
A. 힙은 완전 이진 트리이므로 배열 인덱스로 부모/자식을 O(1)에 계산 가능합니다.
Q. Heapify가 O(n)인 이유?
A. 아래에서 위로 처리하면, 깊은 노드는 적게 이동하고 얕은 노드는 많이 이동합니다. 수학적으로 합하면 O(n)입니다.