K-D heap

A 2-d heap with 20 elements.

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 k keys (or priorities), 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(n) time. The following operations are supported:

Importantly, the hidden constant in these operations is exponentially large relative k, the number of dimensions, so K-D heaps are not practical for applications with very many dimensions.