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.
Implementation
The kinetic hanger structure is exactly the same as the kinetic heap structure, but without the balancing requirement. Thus, it consists of an efficientpriority queue to maintain the certificate failure times, as well as a main heap-like tree structure in which the elements are stored. There is a certificate associated with each edge that enforces the heap property along that edge. The characteristic operation in a kinetic hanger is "hanging", which is defined as follows. Hang
If there is no element at n, put e in n and return
If the element x in n has a higher priority than e, choose a child c of n randomly and recursively call Hang
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
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:
Build-hanger: First sort elements by priority and then call hang on the root for each element in order. Then calculate and schedule certificate failure times in the event queue. This takes O time, similar to a kinetic heap.
Insert: The kinetic hanger inserts top-down by "hanging" the new element at the root node. This takes O time, but O certificates might have to be changed on the way down, thus total time is O
Delete: This is a simpler operation than in a heap, since the balancing of tree structure doesn't need to be maintained. Thus, the element is simply replaced with the larger of its children, and then that child is recursively deleted. Again, this takes O time, but O certificates might have to be updated, so the total time is O.
All these operations result in a uniformly random structure for the hanger, with an expected height of O.
Analysis
This structure is:
Responsive: processing a certificate failure takes O time, just like in a kinetic heap
Local: each element is involved in O certificates, just like in a kinetic heap
Compact: there are a total of O certificates, just like in a kinetic heap
