피보나치 힙 연산 계산기

배열 기반 이진 힙과 달리 삽입과 두 힙의 병합(union)을 O(1)에 처리합니다. 새 원소는 독립된 트리 하나로 루트 리스트에 얹기만 하고, union은 두 루트 리스트를 이어 붙이기만 하기 때문입니다. 대신 이렇게 미뤄 둔 정리 비용을 extractMin이 호출될 때 한꺼번에 치릅니다.

최솟값을 떼어내고 그 자식들을 루트로 올린 �며, 차수(자식 수)가 같은 트리끼리 계속 합쳐(consolidate) 트리 개수를 O(log n)개로 줄입니다. 이 합치는 작업은 당장은 시간이 걸리지만, 그만큼 이전의 O(1) 삽입들이 미뤄 둔 비용을 갚는 것이라 여러 번의 연산에 걸쳐 평균을 내면(상각) O(log n)이 됩니다.

값을 줄여서 부모보다 작아지면 그 노드를 부모에서 잘라(cut) 루트 리스트로 바로 올립니다. 이미 자식을 한 번 잃은 부모(mark 표시됨)에서 또 자식이 잘리면 그 부모도 연쇄적으로 잘라 올리는데(cascading cut), 이 연쇄 자르기 덕분에 트리 모양이 너무 망가지지 않으면서도 각 cut 자체는 O(1)에 끝납니다.

CLRS(Cormen 등) 교과서의 표준 알고리즘을 그대로 구현해, 입력한 숫자들로 실제 피보나치 힙을 만들고 union·extractMin·전체 정렬까지 실행한 결과를 보여줍니다. 겉으로 보이는 트리 개수·차수 변화가 알고리즘이 실제로 만들어 내는 값입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.