피보나치 힙 편집하기 (부분)

==연산==
피보나치 힙이 지원하는 주요 연산과 시간 복잡도는 다음과 같다.
*삽입(Insert): O(1) 암묵적 시간
*최소값 찾기(Find-Min): O(1)
*최소값 삭제(Delete-Min): O(log n) 상환 시간
*키 감소(Decrease-Key): O(1) 상환 시간
*삭제(Delete): O(log n) 상환 시간
*합치기(Merge): O(1)
그 구체적인 과정은 다음과 같다.
===삽입(Insert)===
*새로운 노드를 생성하여 별개의 트리로 루트 리스트에 삽입한다.

*삽입 후, 기존 최소 노드와 비교하여 새로운 노드가 더 작으면 최소 노드 포인터를 갱신한다.

*루트 리스트에 단순히 추가하는 방식이므로 시간 복잡도는 O(1)이다.
===최소값 찾기(Find-Min)===
*최소 노드를 가리키는 포인터를 직접 반환한다.

*힙의 구조를 탐색하거나 변경하지 않으므로 시간 복잡도는 O(1)이다.
===합치기(Merge)===
*두 피보나치 힙의 루트 리스트를 단순히 병합한다.

*두 힙 각각의 최소 노드 포인터 중 더 작은 값을 새로운 최소 노드로 설정한다.

*포인터 조작만으로 수행되기 때문에 시간 복잡도는 O(1)이다.
===키 감소(Decrease-Key)===
*대상 노드의 키 값을 새로운, 더 작은 값으로 갱신한다.

*갱신된 키가 부모 노드보다 작은 경우:
**해당 노드를 잘라 루트 리스트로 이동시킨다.
**부모 노드를 검사하여 마크되지 않았다면 마크한다.
**이미 마크되어 있다면 부모 노드도 잘라서 루트 리스트로 이동시키고, 이 과정을 조상 노드까지 반복한다(연쇄 절단, Cascading Cut).

*이 절단 과정은 힙의 평탄화(flattening)를 도와 이후 연산의 효율성을 보장한다.

*상환 시간 복잡도는 O(1)이다.
===삭제(Delete)===
*삭제하려는 노드의 키를 현재 최소 키보다 더 작게 설정한다(Decrease-Key).

*그런 다음, Delete-Min 연산을 호출하여 해당 노드를 삭제한다.

*Delete-Min을 거쳐야 하므로 시간 복잡도는 O(log n)이다.
===최소값 삭제(Delete-Min)===
*현재 최소 노드를 제거한다.

*제거한 최소 노드의 모든 자식 노드를 루트 리스트에 추가한다. 이때 각 자식 노드는 부모 포인터를 초기화한다.

*루트 리스트 내에서 동일한 차수(degree)를 가진 트리들을 병합(consolidate)하여 하나의 트리로 만든다.
**각 병합은 두 트리의 루트 중 더 작은 키를 가진 것을 새로운 루트로 선택한다.
**병합 후 차수는 증가한다.

*병합이 완료되면, 루트 리스트에서 가장 키가 작은 노드를 새로운 최소 노드로 설정한다.

*시간 복잡도는 O(log n) (상환)이다.