Kinetic hanger explained

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 (the priority of each element is higher than the priority of its children) 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.

Implementation

The kinetic hanger structure (including certificates and event queue) is exactly the same as the kinetic heap structure, but without the balancing requirement. Thus, it consists of an efficient priority queue (the event queue) to maintain the certificate failure times, as well as a main (not necessarily balanced) heap-like tree structure in which the elements are stored. There is a certificate associated with each edge that enforces the heap property (priority of parent > priority of child) along that edge.

The characteristic operation in a kinetic hanger is "hanging", which is defined as follows (a distinction is made between a node in the tree structure and the element stored in it).Hang(Node n, Element e)

  1. If there is no element at n, put e in n and return
  2. If the element x in n has a higher priority than e, choose a child c of n randomly and recursively call Hang(c, e)
  3. If the element x in n has a lower priority than e, put e in n choose a child c of n randomly and recursively call Hang(c, x)

The main difference between the kinetic hanger and the kinetic heap is in the key operations, which are implemented as follows in a kinetic hanger:

All these operations result in a uniformly random structure for the hanger, with an expected height of O(log n).

Analysis

This structure is:

References