Multidimensional heaps and complementary range searching

We discuss multidimensional heaps, that is, heaps in which each element has a d-tuple of keys and we can find and delete the minimum element for each coordinate. These structures are a reasonable generalization of double-ended heaps, and can be realized with O(1) insert, merge, findmin and O(logn) deletemin, or with O(logn) insert, and O(1) findmin, deletemin, all these times being worst-case. We also apply these structures to the problem of complementary range searching, improving on the performance of d-dimensional interval heaps introduced by van Leeuwen and West.