https://svn.boost.org/trac10/ticket/379 <pre class="wiki">There are many types of heaps that provide good theoretical performance when used as a priority queue, e.g., by Dijkstra's shortest paths algorithm. The BGL contains implementations of two such data structures: a binary heap and a relaxed heap. The latter is used because it has been shown to provide the best overall performance. However, we should investigate other kinds of heaps, e.g., Fibonacci heaps, relaxed Fibonacci heaps, and run-relaxed heaps, to determine which option is best for the BGL. Dietmar Kuhl implemented several kinds of heaps in his Heaps library, which could be found in earlier versions of Boost. It was removed from Boost in the 1.27.0 timeframe because it had never been reviewed and was not maintained, but may still prove valuable for experiments. </pre> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/379 Trac 1.4.3 Douglas Gregor Tue, 22 Nov 2005 13:59:34 GMT https://svn.boost.org/trac10/ticket/379#comment:1 https://svn.boost.org/trac10/ticket/379#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> </ul> <pre class="wiki">Logged In: YES user_id=249098 "The lore" seems to indicate that relaxed heaps are good enough. If we find performance problems later or someone codes a better priority queue, we'll consider it at that time. </pre> Ticket