테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 피보나치 힙 ======
  * [[https://en.wikipedia.org/wiki/Fibonacci_heap|위키피디아]]
  * 피보나치 힙을 처음 접하는 것은 보통 Dijkstra's algorithm이나 Prim's algorithm을 배울 때이다. 시간복잡도를 놀랍게 단축해 줄 수 있다고 전해진다.
    * 일반적인 바이너리 힙과 달리, 삽입과 decrese-key 연산을 O(logn)이 아닌 O(1)에 처리할 수 있다고 한다
  * 그러나 일반 수업이나 강좌에서 피보나치 힙을 구현시키는 경우는 아직 들어본 적이 없고, Dijkstra's algorithm이나 Prim's algorithm을 구현시킬 때도 바이너리 힙을 사용하게 한다.
  * 이론적으로 빅오 복잡도는 바이너리 힙에 비해서 빠른게 맞지만, 앞에 붙는 상수가 너무 크기 때문에, 실질적으로 구현하게 되는 n의 범위에서는 바이너리 힙을 사용한 구현보다 느린것 같다.
    * 시간날때 한번 실제로 테스트 해볼까..
  * 파이썬으로된 구현은 이런 것들이 있는듯 하니, 써보는 데에 어려움은 없을 듯
    * https://github.com/quangntran/fibheap
    * https://github.com/danielborowski/fibonacci-heap-python
    * https://github.com/ivan-ristovic/fheap