Kinetic Heap

Kinetic heap is an event-driven priority queue within computation and algorithms designed to maintain the minimum (or maximum) element among a set of n items whose numerical keys vary continuously with time t. Introduced by Julien Basch, Leonidas J. Guibas, and John Hershberger at the 1997 ACM–SIAM Symposium on Discrete Algorithms (SODA) and published in the Journal of Algorithms in 1999 as the foundational example of the kinetic data structure (KDS) framework, a kinetic heap augments a classical binary heap with algebraic certificates on every parent–child edge and schedules each certificate's expiration time in a global event queue. Together with its companion kinetic priority queues—the kinetic tournament, the kinetic hanger, and the kinetic heater—the kinetic heap serves as the core event-scheduling engine inside kinetic geometric algorithms for collision detection, kinetic convex hulls, kinetic closest pairs, and dynamic visibility maintenance.

Unlike static priority queues such as the Fibonacci heap, pairing heap, or violation heap, which only modify keys at discrete caller-initiated operations, a kinetic priority queue treats each item's key as a known continuous trajectory k_i(t) (most commonly an affine linear function k_i(t) = a_i t + b_i or a bounded-degree polynomial) and advances through time by repairing the heap only at the discrete instants when a child's key overtakes its parent's key.

Let S = {1, 2, ..., n} be a set of n elements, where the priority of each element i ∈ S is a continuous, piece-wise algebraic function of time t ∈ [0, ∞):

k_i(t) = a_i t + b_i

(or more generally a degree-s algebraic trajectory such that any pair of trajectories k_i(t) and k_j(t) intersect at most s times). A kinetic priority queue must maintain a pointer to the element attaining the instantaneous minimum key:

i^*(t) = arg min_{i ∈ S} k_i(t)

as time t advances continuously, while also supporting three dynamic operations at arbitrary times t:

• Insert(i, k_i(t)): Add a new element i with trajectory k_i(t) to S at the current time t.
• Delete(i): Remove element i from S at time t.
• Change-Trajectory(i, k′_i(t)): Replace the motion law of element i at time t with a new trajectory k′_i(t) satisfying k′_i(t) = k_i(t) (corresponding to an elastic collision, control impulse, or flight-plan update).

Geometrically, in the (t, k)-plane, the trajectories k₁(t), ..., k_n(t) form an arrangement of n lines (or pseudo-segments), and maintaining the minimum element i^*(t) is equivalent to tracking the lower envelope of the line arrangement as a vertical sweep line moves rightward with increasing t. Whenever the current minimum line intersects another line and ceases to be the lowest trajectory, an external event occurs; any structural rearrangement performed by the data structure among non-minimum elements is an internal event.

Binary Tree Structure and Parent–Child Certificates

A kinetic heap stores the n elements in a balanced binary tree—typically a complete binary tree of height ⌊log₂ n⌋—that satisfies the standard min-heap structural invariant at the current time t₀: for every tree edge linking a parent node u to a child node v, the instantaneous keys obey:

k_u(t₀) ≤ k_v(t₀)

To kinetize this static binary heap within the kinetic data structure paradigm, each parent–child edge (u, v) is equipped with an elementary inequality certificate [u ≤ v] asserting that k_u(t) ≤ k_v(t). Because a tree on n nodes has n − 1 edges, a kinetic heap maintains n − 1 certificates in total.

Certificate Failure Times and the Global Event Queue

For each parent–child edge (u, v) with affine trajectories k_u(t) = a_u t + b_u and k_v(t) = a_v t + b_v that currently satisfies k_u(t₀) ≤ k_v(t₀), the certificate [u ≤ v] can only fail at a future time t > t₀ if the child's key decreases faster (or increases more slowly) than the parent's key—that is, if the relative slope satisfies a_v < a_u (or, for general algebraic trajectories, at the earliest root t > t₀ of k_u(t) − k_v(t) = 0). Specifically, for linear trajectories:

• If a_u ≤ a_v, the inequality k_u(t) ≤ k_v(t) remains valid for all t ≥ t₀, so its failure time is t_fail(u, v) = +∞ (an inactive certificate).
• If a_u > a_v, the two lines cross at the exact future expiration timestamp:

t_fail(u, v) = (b_v − b_u) / (a_u − a_v) ≥ t₀

All active certificates with finite failure times t_fail < +∞ are stored in a conventional static priority queue Q—called the global event queue—keyed by their scalar expiration timestamps t_fail. Because the timestamps t_fail are static real numbers rather than moving functions of time, Q can be implemented as a standard binary heap, Fibonacci heap, or radix heap.

Certificate Expiration and Local Swap Repair

When time t reaches the minimum timestamp t_fail(u, v) at the head of the global event queue Q, the child v is overtaking its parent u (k_v(t) = k_u(t) and a_v < a_u). The kinetic heap repairs the violation in O(1) tree-pointer updates and O(log n) event-queue operations:

1. Parent–Child Swap: Swap the elements stored at parent u and child v inside the binary heap tree. If u was the root of the kinetic heap, v becomes the new overall minimum element (triggering an external event for the calling algorithm).
2. Certificate Replacement: Swapping u and v invalidates only the certificates incident to the tree positions of u and v. In a binary tree, at most five tree edges are incident to the pair (u, v):
   • The edge (u, v) itself, whose certificate reverses from [u ≤ v] to [v ≤ u] with failure time +∞ (since a_v < a_u means v will remain smaller than u for all future t > t_fail under linear motion).
   • The edge from u's parent p to the upper node position (if u was not the root), whose certificate becomes [p ≤ v].
   • The edge from the upper node position to u's other child w (the sibling of v), whose certificate becomes [v ≤ w].
   • The two edges from the lower node position (now holding u) to the two original children x and y of v, whose certificates become [u ≤ x] and [u ≤ y].
3. Event Queue Rescheduling: Compute the new failure times for these at most four adjacent edges and update their entries in the global event queue Q (each taking O(log n) time in Q). Because k_u(t_fail) = k_v(t_fail) at the exact instant of crossing, all four adjacent inequalities [p ≤ v], [v ≤ w], [u ≤ x], and [u ≤ y] are guaranteed to hold at t = t_fail without cascading further swaps at that instant.

Basch, Guibas, and Hershberger evaluated every kinetic data structure along four asymptotic criteria:

1. Responsiveness: The worst-case time required to process a single certificate failure and restore the invariant. In a kinetic heap, swapping u and v updates at most 4 other certificates in the event queue Q of size ≤ n − 1, so each event takes O(log n) worst-case time; therefore the kinetic heap is responsive.
2. Locality: The maximum number of certificates in which any single element i participates, which governs the cost of Change-Trajectory(i, k′_i(t)). Because a binary tree node has at most 1 parent and at most 2 children, every element in a kinetic heap participates in at most 3 certificates (O(1) locality). Consequently, when an element changes trajectory after a collision, only at most 3 entries in Q need to be recomputed, taking O(log n) time.
3. Compactness: The total number of active certificates maintained by the structure. A kinetic heap stores n − 1 parent–child certificates, achieving optimal O(n) compactness.
4. Efficiency: The ratio between the worst-case total number of internal certificate-failure events processed by the data structure and the worst-case number of external events (changes to the true minimum i^*(t)). By Davenport–Schinzel theory, the lower envelope of n lines in the plane has at most n − 1 vertices (Ω(n) external events in the worst case), and for degree-s trajectories the complexity is λ_s(n) = n 2^{Θ(α(n)s−2)}. Because a polylogarithmic factor log^c n is negligible compared to n, a KDS is called efficient if its total event count is O(n polylog n).

Sweeping Analysis of Total Events in a Kinetic Heap

Determining the exact worst-case number of certificate failures in a kinetic heap with n linear trajectories k_i(t) = a_i t + b_i was a classic problem in kinetic geometry:

• Basch, Guibas, and Hershberger (1999) proved an initial upper bound of O(n log³ n) total events by defining a potential function on each tree node that counts how many descendants have both a currently larger key k_v(t) > k_u(t) and a smaller slope a_v < a_u ("inversion potential" at tree levels).
• Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Paulo C. P. Carvalho (2001) tightened the analysis of the kinetic heap to O(n log² n) worst-case events for linear trajectories—matching the asymptotic event bound of the kinetic tournament without sacrificing O(1) locality! Their proof defines, for each time t and each tree edge e, the imbalance between the slopes of subtrees and shows via a binary representation of subtree weights that the sum of potential drops across all levels of the complete binary tree is bounded by O(n log² n).

To explore trade-offs between the O(n log² n) event count of a deterministic kinetic heap and the Ω(n log n) information-theoretic sorting barrier across all tree levels, researchers developed three closely related kinetic priority queues:

Kinetic Tournament

A kinetic tournament (Basch, Guibas, and Hershberger, 1999) organizes the n elements at the leaves of a complete binary tournament tree of height ⌈log₂ n⌉. Every internal node w stores the winner (minimum key at time t) of its two child subtrees w_left and w_right, certified by a single comparison certificate [winner(w_left) ≤ winner(w_right)].

• Events and Efficiency: By applying a divide-and-conquer recurrence across the ⌈log₂ n⌉ levels of the tournament—where an internal node covering m leaves experiences as many events as the lower envelope of m trajectories, O(m) for lines or λ_s(m) for degree-s curves—the total number of events across all internal nodes is ∑_h=1^{log n} (n / 2^h) O(2^h) = O(n log n) for linear trajectories (and O(λ_s(n) log n) for degree-s trajectories).
• Locality Penalty: Because the winning element at the root must appear at every ancestor along its root-to-leaf path, a single element can participate in Θ(log n) certificates (O(log n) locality), and when an internal certificate fails at height h, the new winner must percolate up through up to h ancestor comparisons, costing O(log² n) worst-case time per event or flight-plan update.

Kinetic Hanger

Introduced by Haim Kaplan, Robert E. Tarjan, and Kostas Tsioutsiouliklis (2001), a kinetic hanger is a randomized variant of the kinetic heap that avoids maintaining a fixed complete binary tree shape. When a new element is inserted (or during initial construction), it hangs down from the root by choosing left or right child branches independently at random with probability 1/2 at each step until reaching an empty child slot, while certificate expirations swap parent and child in place exactly as in a kinetic heap.

• Because the expected depth of any node is O(log n) and each node still has at most 1 parent and 2 children, a kinetic hanger preserves O(1) worst-case locality (at most 3 certificates per item) and O(log n) expected responsiveness, while reducing the expected total number of certificate failures on linear trajectories from O(n log² n) down to O(n log n) expected events.

Kinetic Heater

Also introduced by Basch, Guibas, and Hershberger (1999), a kinetic heater applies the random-priority principle of a treap to kinetic priority queues. Each element i is assigned a static random priority p_i in addition to its time-varying key k_i(t): the binary tree is a binary search tree on the static priorities p_i and a min-heap on the kinetic keys k_i(t). When a child's key k_v(t) overtakes its parent's key k_u(t), the heater performs a single tree rotation (as in a treap or splay tree) rather than an in-place node swap, achieving O(1) locality and O(n α(n) log n) expected events.

Kinetic heaps and their tournament/hanger counterparts appear across dynamic and kinetic geometry:

1. Hierarchical Kinetic Data Structures and the Global Event Queue: Every kinetic data structure—such as the kinetic Delaunay triangulation, kinetic convex hull, or kinetic closest pair—produces certificates whose failure times may themselves depend on sub-structures. When a geometric algorithm nests kinetic structures hierarchically, a kinetic heap or kinetic tournament maintains the earliest expiring event across mobile sub-components.
2. Continuous Collision Detection and Molecular Dynamics: In hard-sphere gas simulations, robotic motion planning, and rigid-body physics engines, pairwise time-of-impact functions between moving bounding volumes or Voronoi cells are tracked by kinetic priority queues, exploiting the O(1) locality of the kinetic heap or kinetic hanger so that when two particles collide and change velocity trajectories, only 3 certificates per affected pair need to be rescheduled.
3. Parametric Shortest Paths and Parametric Minimum Spanning Trees: In networks whose edge weights vary linearly with a parameter λ (w_e(λ) = a_e λ + b_e), sweeping λ from −∞ to +∞ inside Prim's algorithm or Dijkstra's algorithm reduces to maintaining kinetic priority queues over the cut edges, locating all breakpoints of the parametric minimum spanning tree piece-wise linear weight curve.

When a parent and child swap in a kinetic heap at time t_fail, can the swap immediately trigger another swap at the exact same timestamp?

Under general position (where no three trajectories pass through a common point at the same instant t_fail), a swap between parent u and child v at t = t_fail never triggers an immediate cascading swap. Because k_u(t_fail) = k_v(t_fail) at the exact moment of intersection, replacing u with v below u's parent p preserves k_p(t_fail) ≤ k_u(t_fail) = k_v(t_fail), and placing u above v's children x, y preserves k_u(t_fail) = k_v(t_fail) ≤ min(k_x(t_fail), k_y(t_fail)). Thus all four updated adjacent certificates have failure times ≥ t_fail.

Why do we still need a static priority queue Q if we already have a kinetic heap?

The kinetic heap orders elements by their time-varying keys k_i(t), which change continuously and change relative rank as trajectories cross. However, to know when the next crossing will happen inside the kinetic heap, the simulation must find the minimum among the static scalar failure timestamps t_fail(u, v) ∈ ℝ of the n − 1 parent–child certificates. Those timestamps are fixed numbers (until a swap or trajectory update modifies at most 4 of them), so a standard static priority queue Q (such as a binary heap or Fibonacci heap) is used as the global event scheduler.

When should an engineer choose a kinetic heap over a kinetic tournament?

A kinetic heap (or randomized kinetic hanger) is preferred whenever items frequently undergo trajectory updates (Change-Trajectory, Insert, or Delete) due to collisions or user steering, because its O(1) locality (at most 3 certificates per item) guarantees O(log n) worst-case time per trajectory update and per event, compared to O(log² n) in a kinetic tournament. Conversely, if trajectories are high-degree curves (s ≥ 3) that rarely change flight plans, a kinetic tournament provides a clean worst-case event bound of O(λ_s(n) log n).

1. Basch, J., Guibas, L. J., & Hershberger, J. (1999). "Data Structures for Mobile Data." Journal of Algorithms, 31(1), 1–28. https://doi.org/10.1006/jagm.1998.0988
2. da Fonseca, G. D., de Figueiredo, C. M. H., & Carvalho, P. C. P. (2001). "Kinetic Heap-Ordered Trees: Tight Analysis and Improved Algorithms." Information Processing Letters, 85(3), 165–169. https://doi.org/10.1016/S0020-0190(02)00368-X00368-X)
3. Kaplan, H., Tarjan, R. E., & Tsioutsiouliklis, K. (2001). "Faster Kinetic Heaps and Their Use in Broadcast Scheduling." In Proceedings of the Twelfth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 836–844. https://dl.acm.org/doi/10.5555/365411.365793
4. Guibas, L. J. (1998). "Kinetic Data Structures: A State of the Art Report." In Robotics: The Algorithmic Perspective (WAFR 1998), pp. 191–209. A. K. Peters. https://doi.org/10.1201/9781439864531
5. Agarwal, P. K., Eppstein, D., Guibas, L. J., & Henzinger, M. R. (1998). "Parametric and Kinetic Minimum Spanning Trees." In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 596–605. IEEE. https://doi.org/10.1109/SFCS.1998.743510