K-D heap


A K-D heap is a data structure in computer science which implements a multidimensional priority queue without requiring additional space. It is a generalization of the Heap. It allows for efficient insertion, query of the minimum element, and deletion of the minimum element in any of the k dimensions, and therefore includes the double-ended heap as a special case.

Structure

Given a collection of n items, where each has keys, the K-D heap organizes them in to a binary tree which satisfies two conditions:
The property of k-d heap order is analogous to that of the heap property for regular heaps. A heap maintains k-d heap order if:
One consequence of this structure is that the smallest 1-st property-element will trivially be in the root, and moreover all the smallest i-th property elements for every i will be in the first k levels.

Operations

Creating a K-D heap from n items takes O time. The following operations are supported:
Importantly, the hidden constant in these operations is exponentially large relative, the number of dimensions, so K-D heaps are not practical for applications with very many dimensions.