Heap-based algorithm for one-dimensional particle systems

Original · EN

A fast algorithm to study one-dimensional self-gravitating systems, and, more generally, systems that are Lagrangian integrable between collisions, is presented. The algorithm is event-driven, and uses a heap-ordered set of predicted future events. In the limit of large number of particles N, the operation count is dominated by the cost of reordering the heap after each event, which goes asymptotically as N. Some applications are discussed in detail.