ps:피보나치

피보나치 힙을 처음 접하는 것은 보통 Dijkstra's algorithm이나 Prim's algorithm을 배울 때이다. 시간복잡도를 놀랍게 단축해 줄 수 있다고 전해진다.

그러나 일반 수업이나 강좌에서 피보나치 힙을 구현시키는 경우는 아직 들어본 적이 없고, Dijkstra's algorithm이나 Prim's algorithm을 구현시킬 때도 바이너리 힙을 사용하게 한다.

이론적으로 빅오 복잡도는 바이너리 힙에 비해서 빠른게 맞지만, 앞에 붙는 상수가 너무 크기 때문에, 실질적으로 구현하게 되는 n의 범위에서는 바이너리 힙을 사용한 구현보다 느린것 같다.

파이썬으로된 구현은 이런 것들이 있는듯 하니, 써보는 데에 어려움은 없을 듯