피보나치 선생님의 엉덩이

요즘 영 머리 안 쓰는 일만 했더니 머리가 굳어가는 기분이 들기 시작해서, 2.4에서 새로 들어가는 collections 모듈의 heap타입을 한 번 구현해 보고 있습니다. heap타입은 일단은 피보나치 힙으로 구현하도록 제안되어있는데, 나중에 같거나 좋은 복잡도를 갖고 아모타이즈드 분석에서 나은 알고리즘이 있다면 다른 걸로 교체할 수도 있다고 합니다. 그래서 일단은 일반적인 힙 작업들을 메쏘드 인터페이스로 만드는 것이 가장 먼저 정해져야할 작업입니다.

옛날에 역시 피보나치 힙으로 구현된 파이썬 모듈인 devel/py-pqueue 소스를 봤을 때 앞쪽 주석이 “이 알고리즘은 매우 더러우니 소스 보고 이해할 생각은 하지 마시오” 식의 문구가 써 있어서 당황해서 안 봤던 기억이 있는데, 웹에서 애플릿 애니메이션을 몇개 보면서 문서를 보니 그런대로 이해는 가는군요. 요즘 세상이 좋아져서.. 흐흐;

우선, insert, min, extractmin은 구현했는데, 이제 decreasekey, union, iterator, delete같은 것만 구현하면 될 것 같습니다. 그런데, 지하철에서 오는 내내 생각하다가 내릴 곳을 놓칠뻔 한 심각한 고민이 문서들을 읽어봐도 해결되지 않는 것이 하나 있습니다. decreasekey 작업을 수행할 때 트리를 가지에서 뚝 떼서 밑둥에 붙이는 작업이 일어나는데, 그럼 그 원래 붙어있던 자리의 degree가 틀린 값을 기록하고 있게 된다는.. 그러니까 원래 degree 4인 것과 degree 1인 자식들이 붙어있던 녀석은 degree가 5가 기록이 되어있겠지만, degree 4인 자식이 decreasekey하던 중 떨어져 나가면, 그 가지는 실제로는 degree 2지만, 값은 5가 기록되어 있게 된다는 것인데.. 이렇게 되면, consolidate하는 과정에서 전체 원소 개수로 추정하는 maxdegree를 넘어 버리는 노드가 나올 수도 있을 것 같고, 무지 컸다가 막 decreasekey되면서 뚝뚝 떨어져 나온 힙이라면, 여기저기 실제 degree보다 엄청 높은 녀석들이 분산돼 있어서, 실제 효율이 많이 떨어지지 않을까 하는 걱정에 휩싸입니다. -.-;;; 흐흐흑… 혹시 피보나치 힙과 친한 분들은 꼭 알려주세요;

-> 후기: 알고보니 degree를 제가 잘못 이해한 것이네요; degree는 높이가 아니라 그냥 자식 노드 갯수를 뜻하는 것이었네요~ (아히 부끄러워라;; )

지금까지 구현한 소스는 http://openlook.org/cvs/collections/ 에 올라가 있습니다. 남은 메쏘드 구현이 끝나면 SF에 올릴 생각입니다.