Kinetic heap

A regular heap can be kinetized by augmenting with a certificate [A>B] for every pair of nodesA, B such that B is a child node of A.

If the value stored at a node X is a function fX(t) of time, then this certificate is only valid while fA(t) > fB(t).

[1][2][3] However, in the special case of affine motion f(t) = at + b of the priorities, kinetic heaps are known to be very efficient.

[2] In this special case, the maximum number of events processed by a kinetic heap can be shown to be exactly the number of edges in the transitive closure of the tree structure of the heap, which is O(nlogn) for a tree of height O(logn).

[2] If n insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is