最短路以外での Binary-Heap - 2。

以下のグラフ・クエリに対し、realloc の性能を調べてみた。

Graph : USA-road-d.NY.gr
Query : random p2p x 256

このクエリでの最大ヒープサイズは 974 である。
以下の実験は、ブロックサイズを変えての実行時間の推移である。

   1 : 4.92[sec]
   8 : 4.94[sec]
  32 : 4.92[sec]
 128 : 4.91[sec]
1024 : 4.91[sec]

一度に確保することで、 4.65 [sec] 程になるが、メモリを大きく抑える事ができることを考えればこれもありだろう。