[vdr] Problems with 20 Timers
olaf at bigred.inka.de
Fri Feb 25 19:16:38 CET 2005
> I wonder if it would be worth rewriting cSchedule to store events in a
> binary tree based on time. A double-linked list could be included in the
> nodes pointing to allow for scanning through the schedule in the
> conventional way (for(cEvent *p = events.First()...)
The right data structure for this (or rather, the canonical data
structure for any sort of timer queue) is a binary heap. Guaranteed
O(log n) time for insert and delete(first) operation and O(1) for
lookup(first), zero memory overhead and much easier to implement than
all other sorts of balanced tree.
> What do people think, would it be worth me writing a patch?
More information about the vdr