Kinetic heap

Last updated January 14, 2021

A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property – if $B$ is a child node of $A$ , then the priority of the element in $A$ must be higher than the priority of the element in $B$ . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue (the event queue) to maintain certificate failure times.

Implementation and operations

A regular heap can be kinetized by augmenting with a certificate [ $A > B$ ] for every pair of nodes $A$ , $B$ such that $B$ is a child node of $A$ . If the value stored at a node $X$ is a function $f X (t)$ of time, then this certificate is only valid while $f A (t) > f B (t)$ . Thus, the failure of this certificate must be scheduled in the event queue at a time $t$ such that $f A (t) > f B (t)$ .

All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take $O(log n)$ time.

Dealing with certificate failures

When a certificate [ $A > B$ ] fails, the data structure must swap $A$ and $B$ in the heap, and update the certificates that each of them was present in.

For example, if $B$ (call its child nodes $Y,Z$ ) was a child node of $A$ (call its child nodes $B,C$ and its parent node $X$ ), and the certificate [ $A > B$ ] fails, then the data structure must swap $B$ and $A$ , then replace the old certificates (and the corresponding scheduled events) [ $A > B$ ], [ $A < X$ ], [ $A > C$ ], [ $B > Y$ ], [ $B > Z$ ] with new certificates [ $B > A$ ], [ $B < X$ ], [ $B > C$ ], [ $A > Y$ ] and [ $A > Z$ ].

Thus, assuming non-degeneracy of the events (no two events happen at the same time), only a constant number of events need to be de-scheduled and re-scheduled even in the worst case.

Operations

A kinetic heap supports the following operations:

$create-heap (h)$ : create an empty kinetic heap $h$
$find-max (h, t)$ (or find-min): – return the $max$ (or $min$ for a $min-heap$ ) value stored in the heap $h$ at the current virtual time $t$ .
$insert (X, f X, t)$ : – insert a key $X$ into the kinetic heap at the current virtual time $t$ , whose value changes as a continuous function $f X (t)$ of time $t$ . The insertion is done as in a normal heap in $O(log n)$ time, but $O(log n)$ certificates might need to be changed as a result, so the total time for rescheduling certificate failures is $O(log 2 n)$
$delete (X, t)$ – delete a key $X$ at the current virtual time $t$ . The deletion is done as in a normal heap in $O(log n)$ time, but $O(log n)$ certificates might need to be changed as a result, so the total time for rescheduling certificate failures is $O(log 2 n)$ .

Performance

Kinetic heaps perform well according to the four metrics (responsiveness, locality, compactness and efficiency) of kinetic data structure quality defined by Basch et al.^[1] The analysis of the first three qualities is straightforward:

Responsiveness: A kinetic heap is responsive, since each certificate failure causes the concerned keys to be swapped and leads to only few certificates being replaced in the worst case.
Locality: Each node is present in one certificate each along with its parent node and two child nodes (if present), meaning that each node can be involved in a total of three scheduled events in the worst case, thus kinetic heaps are local.
Compactness: Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly $n -1$ where $n$ is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.

Analysis of efficiency

The efficiency of a kinetic heap in the general case is largely unknown.^[1]^[2]^[3] However, in the special case of affine motion $f(t) = a t + b$ of the priorities, kinetic heaps are known to be very efficient.^[2]

Affine motion, no insertions or deletions

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(n log n)$ for a tree of height $O(log n)$ .^[2]

Affine motion, with insertions and deletions

If $n$ insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is $O(n{\sqrt {n\log n}}).$ ^[4] However, this bound is not believed to be tight,^[2] and the only known lower bound is $\Omega (n\log n)$ .^[4]

Variants

This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications,^[5] such as:

Fibonacci kinetic heap
Incremental kinetic heap

Other heap-like kinetic priority queues are:

Related Research Articles

Heap (data structure) Computer science data structure

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

In computer science, a priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

Dijkstras algorithm Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations :

The $d$ -ary heap or $d$ -heap is a priority queue data structure, a generalization of the binary heap in which the nodes have $d$ children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., $d$ -ary heaps were invented by Donald B. Johnson in 1975.

In computer science, a finger tree is a purely functional data structure that can be used to efficiently implement other functional data structures. A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, which is where data is stored, and concatenation and splitting logarithmic time in the size of the smaller piece. It also stores in each internal node the result of applying some associative operation to its descendants. This "summary" data stored in the internal nodes can be used to provide the functionality of data structures other than trees.

In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time. Min-max heaps are often represented implicitly in an array; hence it's referred to as an implicit data structure.

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: $for insertion, find-minimum, meld and decrease-key and for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.$

A kinetic data structure is a data structure used to track an attribute of a geometric system that is moving continuously. For example, a kinetic convex hull data structure maintains the convex hull of a group of $moving points. The development of kinetic data structures was motivated by computational geometry problems involving physical objects in continuous motion, such as collision or visibility detection in robotics, animation or computer graphics.$

A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete changes such as insertions or deletions of points rather than continuous motion.

A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set P of n points that are moving continuously with time in a metric space. While many efficient algorithms were known in the static case, they proved hard to kinetize, so new static algorithms were developed to solve this problem.

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", 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.

A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.

A Kinetic Heater is a kinetic priority queue similar to a kinetic heap, that makes use of randomization to simplify its analysis in a way similar to a treap. Specifically, each element has a random key associated with it in addition to its priority. The kinetic heater is then simultaneously a binary search tree on the element keys, and a heap on the element priorities. The kinetic heater achieves (expected) asymptotic performance bounds equal to the best kinetic priority queues. In practice however, it is less efficient since the extra random keys need to be stored, and the procedure to handle certificate failure is a rotation instead of a simple swap.

A Kinetic hanger is a randomized version of a kinetic heap whose performance is easy to analyze tightly. A kinetic hanger satisfies the heap property but relaxes the requirement that the tree structure must be strictly balanced, thus insertions and deletions can be randomized. As a result, the structure of the kinetic hanger has the property that it is drawn uniformly at random from the space of all possible heap-like structures on its elements.

A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum priority element when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.

Kinetic minimum box is a kinetic data structure to maintain the minimum bounding box of a set of points whose positions change continuously with time. For points moving in a plane, the kinetic convex hull data structure can be used as a basis for a responsive, compact and efficient kinetic minimum box data structure.

References

1 2 Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)
1 2 3 4 da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.
↑ da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)
1 2 Basch, J, Guibas, L. J., Ramkumar, G. D. (1997). "Sweeping lines and line segments with a heap". Proceedings of the thirteenth annual symposium on Computational geometry. SCG. ACM. pp. 469–471. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)
↑ K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling" (PDF). Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)^{[ permanent dead link ]}

Guibas, Leonidas. "Kinetic Data Structures - Handbook" (PDF). Archived from the original (PDF) on 2007-04-18. Retrieved May 17, 2012.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[mobile-1] 1 2 Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)

[heap_analysis-2] 1 2 3 4 da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.

[hanger-3] Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)

[sweep-4] 1 2 Basch, J, Guibas, L. J., Ramkumar, G. D. (1997). "Sweeping lines and line segments with a heap". Proceedings of the thirteenth annual symposium on Computational geometry. SCG. ACM. pp. 469–471. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)

[tarjan-5] K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling" (PDF). Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)^{[ permanent dead link ]}

[1]

[2]

[3]

[4]

[5]