레프티스트 힙 병합 계산기
s-value(널 경로 길이) 불변식으로 두 힙을 O(log n)에 병합할 수 있는 포인터 기반 최소 힙의 병합 과정을 스텝별로 보여줍니다.
숫자열 (순서대로 삽입)
원소 개수6
루트(최솟값)1
불변식 확인정상
마지막 삽입(2)의 병합 과정 (재귀 깊이 순)
깊이1: 2이(가) 루트, 9 병합 → 좌우 스왑 (rank 1) 깊이0: 1이(가) 루트, 2 병합 (rank 2)
최종 트리 구조
└─ 1 (rank 2)
├─ 3 (rank 2)
│ ├─ 5 (rank 1)
│ └─ 8 (rank 1)
└─ 2 (rank 1)
└─ 9 (rank 1)괄호 안 rank는 s-value(널 경로 길이)입니다. 모든 노드에서 오른쪽 자식의 rank가 왼쪽 이하로 유지되어, 오른쪽 경로만 타고 내려가는 병합이 항상 O(log n)에 끝납니다.
사용 방법
- 1숫자를 순서대로 입력해 하나씩 삽입합니다.
- 2각 삽입이 기존 힙과 병합되는 재귀 과정을 확인합니다.
- 3최종 트리 구조와 s-value(rank)를 확인합니다.
자주 묻는 질문
두 힙 중 루트 값이 작은 쪽을 새 루트로 삼고, 그 오른쪽 자식과 나머지 힙을 재귀적으로 병합합니다. 병합이 끝난 뒤 오른쪽 서브트리의 s-value가 왼쪽보다 커지면 좌우를 맞바꿔 불변식을 되살립니다.
어떤 노드에서 "가장 가까운 빈 자식"까지의 거리입니다. 레프티스트 힙은 모든 노드에서 오른쪽 서브트리의 s-value가 왼쪽 이하가 되도록 유지합니다 — 그래서 오른쪽 경로(rightmost path)가 항상 가장 짧은 경로가 되고, 그 길이가 O(log n)으로 보장됩니다.
배열 힙은 삽입·삭제가 O(log n)이지만 두 힙을 합치려면 사실상 하나씩 다시 넣어야 해 O(n)이 걸립니다. 레프티스트 힙은 포인터 기반 트리라 병합 자체가 O(log n)입니다 — 병합이 잦은 상황(예: 여러 우선순위 큐를 합쳐야 하는 그래프 알고리즘)에서 유리합니다.
네. 삽입은 "원소 하나짜리 힙과 병합"이고, 최솟값 제거는 "루트를 떼어내고 왼쪽·오른쪽 서브트리를 병합"입니다. 결국 모든 연산이 merge 함수 하나로 환원됩니다.
알아두면 좋은 점
- [5,3,8,1]을 순서대로 삽입했을 때의 최종 트리 구조(루트 1, 왼쪽에 3-5-8로 이어지는 서브트리)를 손으로 계산해 정확히 일치하는지 검증했습니다.
- 무작위 배열 30개에서 힙 정렬(반복적 최솟값 제거) 결과가 Array.sort와 일치하는지, 무작위 삽입·삭제 200회를 섞어도 최소힙 성질과 s-value 불변식이 매 연산 후 계속 성립하는지 확인했습니다.
함께 보면 좋은 도구
힙 만들기 과정숫자 목록으로 이진 힙을 만드는 두 가지 방법(하나씩 삽입 vs 상향식 heapify)을 나란히 돌려 비교·교환 횟수를 세고, 배열과 트리가 어떻게 대응하는지, 루트를 반복해 뽑으면 어떻게 정렬되는지 보여 줍니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.2의 보수 변환N비트 폭에서 정수를 2의 보수 이진 표현으로 바꿔 줍니다.
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.