Re: No 100 HZ timer!

Horst von Brand
2001-04-13T16:11:58Z

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