검색어 입력폼

[자료구조, 알고리즘] [자료구조]피보나치 힙

등록일 2003.12.18 파일확장자압축파일 (zip) | 3페이지 | 가격 1,000원

소개글

간략한 보고서와 함께 코드에 상세한 주석도 달아두었습니다.
피보나치 힙을 이해하는데 도움이 될겁니다.

목차

1.개요
2.알고리즘
3.구현방법
4.구현시 어려웠던점
5.실행결과
6.토의

본문내용

2. 알고리즘
대개의 Heap 은 트리구조의 특성상 연산에 O(logn) 의 시간복잡도를 가진다. 특히 힙의 노드가 변경되어 힙이 재구성되는 Delete 와 Extract-Min 의 경우에는 세가지 힙구조 모두 O(logn) 의 시간복잡도를 가지게 된다.
Fibonacci Heap 에서는 다른 힙들과 달리 이러한 힙구조의 재구성에 걸리는 연산을 최소화 함으로써 Delete 와 Extract-Min 을 제외한 다른 연산에서 Θ(1) 의 시간복잡도를 구현한다. 즉 불필요한 재구성의 과정을 최소로 줄임으로써 이러한 성능을 구현한 것이다.
(아래 과정은 Minimum Fibonacci Heap 을 기준으로 설명한 것이다.)

(1) Insert
새 노드의 추가시에 추가되는 노드의 key값을 현재 힙에 있는 min key 값과 비교하여 업데이트한다. 이러한 Insert 과정은 1번의 연산과정으로 처리가 된다.

(2) Union
두 개의 Fibonacci Heap을 하나로 병합하는 과정에서도 두 힙 모두 min key를 가지는 노드가 루트노드이기 때문에 별도의 처리과정 없이 병합이 가능하다

(3) Extract-Min
힙의 구조가 Minimum Heap 으로 구성되어 있기 때문에 min 노드는 루트노드이다. min 노드를 제거할 때 min 노드의 자식노드들을 새로운 루트리스트로 하여 힙을 재구성한다. 이 과정은 간단한 병합의 연쇄과정으로 이루어지고 O(logn) 의 시간복잡도를 가진다.

(4) Decease-Key
한 노드의 key 값을 감소시키면 힙의 구조에 변경이 불가피하다. Fibonacci Heap 에서는 이러한 과정을 위해 marking을 하는 기법을 사용하여 Θ(1)의 시간구현이 가능하다.

(5) Delete
노드를 삭제하는 과정은 Decrease-Key 와 Extract-Min 의 과정을 통해 실행할 수 있다. Extract-Min 의 과정에서 힙의 재구성이 발생하기 때문에 O(logn) 의 시간복잡도를 가진다.

참고 자료

Introduction to Algorithms
다운로드 맨위로