n-heap。

n-heap とは、１つのノードに対して n 個のノードを子に持つデータ構造である。n が増えることで比較回数が多くなってしまうが、swap 回数が減ることになるので、heap を配列で実装している場合は有効ではないかと考えた。

意外にも n = 2 のときが最も実行時間が短かった。n = 2 のときはもちろん通常のヒープになる。今回の実装では、容易に n を変更できるように実装していたのだが、こういった結果を得られた。

結局、通常のヒープ法が一番良いようだ。

Graph : USA-road-d.USA.gr
Query : USA10.p2p
　(957498, 10453327)
　(19200797, 7727679)
　(13006257, 40639)
　(4314559, 22779984
　(17261435, 8424294)
　(8077810, 13186938)
　(3048748, 1475829)
　(21869636, 3531883)
　(13446936, 4981527)
　(18549540, 3230879)

■unsigned int
n = 2　44.1[sec]
n = 4　41.0[sec]　
n = 8　44.1[sec]

■unsigned long long
n =　2　42.5[sec]
n =　4　48.4[sec]
n =　8　46.8[sec]
n = 10　48.2[sec]
n = 12　53.9[sec]