Kinetic tournament

A Kinetic Tournament is a kinetic data structure that functions as a priority queue for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner" (maximum or minimum element), with the certificates enforcing the winner of each "match" in the tournament. It supports the usual priority queue operations - insert, delete and find-max. They are often used as components of other kinetic data structures, such as kinetic closest pair.

Implementation

A kinetic tournament is organized in a binary tree-like structure, where the leaves contain the elements, and each internal node contains the larger (or smaller) of the elements in its child nodes. Thus, the root of the tree contains the maximum (or minimum) element at a given time. The validity of the structure is enforced by creating a certificate at each node, which asserts that the element in the node is the larger of the two children. When this certificate fails, the element at the node is changed (to be the element in the other child), and a new certificate representing the new invariant is created. If the element this node was a winner at its parent node, then the element and certificates at the parent must be recursively updated too.

Analysis

This is a O(n) space, responsive, local, compact and efficient data-structure.

References

    Basch, J. 1999. Kinetic data structures. Ph.D. thesis, Dept. Computer Science, Stanford University.

    This article is issued from Wikipedia - version of the Wednesday, May 07, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.