COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 8 years ago

#300 new enhancement

Faster building of heaps

Reported by: kpeter Owned by: alpar
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

For some heap structures it is possible to build them from an existing list of n items faster than calling push() n times.
E.g. for binary heap calling push() for each item takes O(n log n) time, while a heap can be built in O(n) time.

It would be nice to indroduce build() (or something like that) member functions into those heap structures, for which it could be done faster than calling push() n times. Or maybe such a function could be introduced to the heap concept itself and all the heap structures (it could be implemented by calling push(), if it is not slower).

The main reason why we have heaps is to use them in algorithms like Dijkstra and Prim. These algorithms do not need such a function, but if one would like to use LEMON heaps for other purposes, it may be useful.

Change History (1)

comment:1 Changed 8 years ago by kpeter

  • Milestone LEMON 1.2 release deleted
Note: See TracTickets for help on using tickets.