Ben Greear <greearb@candelatech.com> said:
[...]
> Wouldn't a heap be a good data structure for a list of timers? Insertion
> is log(n) and finding the one with the least time is O(1), ie pop off the
> front.... It can be implemented in an array which should help cache
> coherency and all those other things they talked about in school :)
Insertion and deleting the first are both O(log N). Plus the array is fixed
size (bad idea) and the jumping around in the array thrashes the caches.
-- Horst von Brand vonbrand@sleipnir.valparaiso.cl Casilla 9G, Vin~a del Mar, Chile +56 32 672616 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Apr 15 2001 - 21:00:21 EST