힙 (Heap)

부모가 항상 자식보다 작은(최소 힙) 완전 이진트리를 확인하세요. 새 값을 넣으면 부모와 비교하며 위로 떠오르고(sift-up), 최솟값을 꺼내면 마지막 값이 루트로 내려와 자식과 비교하며 아래로 가라앉습니다(sift-down). 트리와 배열을 동시에 보여줘 "배열 하나로 트리를 표현한다"는 힙의 핵심을 체감할 수 있습니다.

배열 표현 (부모 i → 자식 2i+1, 2i+2)

재생 버튼을 누르거나 다음 단계 버튼으로 힙 연산을 시작하세요.

insert 0회 · extractMin 0회

1 / 1

속도

힙 내부 값 방금 삽입된 값 비교 중인 값 교환 후 정착 위치

PSEUDOCODE

insert(value): 배열 끝에 추가  sift-up: 부모보다 작으면 교환하며 위로 이동extractMin(): 루트(최솟값)를 반환할 값으로 저장  마지막 값을 루트로 옮기고 배열 끝 제거  sift-down: 더 작은 자식과 비교해 교환하며 아래로 이동

어떻게 동작하나요

힙은 "부모가 항상 자식보다 작다(최소 힙)"는 규칙만 지키는 완전 이진트리입니다 — 왼쪽/오른쪽 크기 순서는 정해져 있지 않아 BST보다 규칙이 느슨한 대신, 항상 균형 잡힌 모양을 유지해 삽입·삭제가 O(log n)으로 보장됩니다. 배열 하나로 트리 전체를 표현할 수 있는 것도 특징입니다 — 인덱스 i의 부모는 (i-1)/2, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2로 계산되어 별도의 포인터가 필요 없습니다. "최솟값을 항상 O(1)에 확인하고 O(log n)에 꺼낼 수 있다"는 성질 덕분에 우선순위 큐의 기본 구현으로 널리 쓰입니다.

시간·공간 복잡도

insert: O(log n)
extractMin: O(log n)
peek (최솟값 조회): O(1)
임의 값 검색: O(n) (정렬 순서가 없음)
공간 복잡도: O(n)

"힙 정렬 체감" 시나리오에서 extractMin을 반복하면 값이 오름차순으로 하나씩 나옵니다 — 힙 정렬(Heap Sort)이 바로 이 원리를 이용합니다.

다른 자료구조(이진 탐색 트리)도 이어서 시각화할 예정입니다 — Algorithm 코스로 돌아가기

1:1 정원제 · 상시 모집

자료구조도 손으로 직접 다뤄봐야 오래 남습니다

당신에게 맞는 커리큘럼은 1:1 상담에서부터 시작됩니다.

1:1 상담 신청하기