This structure allows one to dynamically maintain the median. Another example is a generalization of interval heaps for the case of multidimensional data, which is called a d-interval heap . One could associate any type of objects to the nodes and impose any ordering relation between the objects at the nodes that is consistent with the idea of heaps, to obtain some kind of object heap . Therefore, one can easily implement this implicit data structure, due to the fact that every location of the array H holds two values except possibly for the last location, which contains either one or two values, depending on whether the mutliset size is odd or even. An n-node interval heap represents a multiset of 2n 1 or 2n elements.
Every node is an interval except for the L-node .
By inserting elements into an initially empty interval heap , it is clear that every finite multiset can be represented as an interval heap . Let I be an interval heap . Now trickle down the value x until there is an underlying heap once more. Construction of an n-node interval heap from a given multiset of 2n 1 or 2n values in arbitrary order can be accomplished in linear time. Then, the heap property for I can be restored in time proportional to the maximum of the depths of I1 and I2 .