> The pending event set is typically organized as a priority queue, sorted by event time. That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Several general-purpose priority queue algorithms have proven effective for discrete-event simulation, most notably, the splay tree. More recent alternatives include skip lists, calendar queues, and ladder queues.
Perhaps it is important to distinguish "logical" and "physical" mutability. I say this because reading a splay tree doesn't change the return value in the future even though it changes the internals.
4 comments
[ 3.2 ms ] story [ 28.8 ms ] thread> The pending event set is typically organized as a priority queue, sorted by event time. That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Several general-purpose priority queue algorithms have proven effective for discrete-event simulation, most notably, the splay tree. More recent alternatives include skip lists, calendar queues, and ladder queues.
Perhaps it is important to distinguish "logical" and "physical" mutability. I say this because reading a splay tree doesn't change the return value in the future even though it changes the internals.