Opened 15 years ago
Last modified 15 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.