The K-D heap: An efficient multi-dimensional priority queue Conference

Ding, Y, Weiss, MA. (1993). The K-D heap: An efficient multi-dimensional priority queue . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 709 LNCS 302-313. 10.1007/3-540-57155-8_257

cited authors

  • Ding, Y; Weiss, MA


  • This paper presents the k-d heap, an efficient data structure that implements a multi-dimensional priority queue. The basic form of the k-d heap uses no extra space, takes linear time to construct, and supports instant access to the items carrying the minimum key of any dimension, as well as logarithmic time insertion, deletion, and modification of any item in the queue. Moreover, it can be extended to a multi-dimensional double-ended mergeable priority queue, capable of efficiently supporting all the operations linked to priority queues. The k-d heap is very easily implemented, and has direct applications.

publication date

  • January 1, 1993

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 302

end page

  • 313


  • 709 LNCS