Data Structures

Balanced search tree

Heater

A heater is a data structure that combines features of heaps and binary trees. Nodes are labelled with two kinds of keys:

• Element keys, that encode relevant information about the problem at hand. In our case, this would be the height of the arc at the actual sweep meridian.
• Priority keys, random numbers assigned to each element. This random priority may be simply a random real number in the interval [0,1] (in the examples below, natural numbers have been used instead, just for making it easier to follow).

Heaters are dynamic structures in that they support efficiently insertion and deletion operations. Insertions are performed in two steps: first, bring the node to be inserted to a leaf position according to the in-order of its priority key (first two images), afterwards perform the necessary rotations to bring it to its correct heap position, as corresponds to the element key (second two images).

Deletions are performed similarly: first, perform the necessary rotations to bring the node to be deleted to a leaf position according to the in-order of its priority key, afterwards eliminate it.