A K-D heap [1] is a data structure in computer science which implements a multidimensional priority queue without requiring additional space. It is a generalization of the Heap. [2] 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.
Given a collection of n items, where each has 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.
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 , the number of dimensions, so K-D heaps are not practical for applications with very many dimensions.
A K-D heap [1] is a data structure in computer science which implements a multidimensional priority queue without requiring additional space. It is a generalization of the Heap. [2] 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.
Given a collection of n items, where each has 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.
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 , the number of dimensions, so K-D heaps are not practical for applications with very many dimensions.