COIN-OR::LEMON - Graph Library

Opened 15 years ago

Last modified 14 years ago

#300 new enhancement

Faster building of heaps

Reported by: Peter Kovacs Owned by: Alpar Juttner
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 14 years ago by Peter Kovacs

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