KD heap ^{[ 1 ]} เป็นโครงสร้างข้อมูลในวิทยาการคอมพิวเตอร์ที่ใช้คิวลำดับความสำคัญ แบบหลายมิติ โดยไม่จำเป็นต้องใช้พื้นที่เพิ่มเติม เป็นการขยายความของHeap [ ^{2 ] ช่วยให้สามารถแทรกข้อมูล ค้นหาองค์ประกอบขั้นต่ำ และลบองค์ประกอบขั้นต่ำในมิติ k ใดๆ ได้}อย่างมีประสิทธิภาพ ดังนั้นจึงรวมถึงdouble-ended heapเป็นกรณีพิเศษด้วย

กำหนดให้มีชุด สิ่งของ nชิ้น โดยแต่ละชิ้นมี${\displaystyle k}$คีย์ (หรือลำดับความสำคัญ) นั้น ฮีป KD จะจัดเรียงคีย์เหล่านั้นลงในโครงสร้างต้นไม้ไบนารีซึ่งเป็นไปตามเงื่อนไขสองประการ:

• เป็นต้นไม้ไบนารีสมบูรณ์ซึ่งหมายความว่ามันเต็มแล้ว ยกเว้นอาจจะเป็นชั้นสุดท้าย ที่ต้องเติมข้อมูลจากด้านซ้ายเข้าไป
• มันตรงตามลำดับฮีป kd

คุณสมบัติของลำดับ kd ในฮีปนั้นคล้ายคลึงกับคุณสมบัติของ ฮี ปทั่วไป ฮีปจะรักษาระดับลำดับ kd ได้ก็ต่อเมื่อ:

• โหนดที่รากมีค่าคุณสมบัติอันดับแรกน้อยที่สุดในต้นไม้ทั้งหมด และ
• โหนดอื่น ๆ ทุกโหนดvที่ไม่ใช่โหนดราก จะต้องมีคุณสมบัติที่ว่า ถ้าโหนดแม่wมีคุณสมบัติที่ i ที่เล็กที่สุดในซับทรีที่มีโหนดแม่เป็นรากแล้วv ก็ จะมีคุณสมบัติที่ i ที่เล็กที่สุด เช่นกัน${\displaystyle (i\mod k)+1}$คุณสมบัติที่ -th ของซับทรีทั้งหมดที่มีรากเป็นv

ผลลัพธ์ประการหนึ่งของโครงสร้างนี้คือ องค์ประกอบคุณสมบัติลำดับที่ 1 ที่เล็กที่สุดจะอยู่ในรากโดยปริยาย และยิ่งไปกว่านั้น องค์ประกอบคุณสมบัติลำดับที่ i ที่เล็กที่สุดทั้งหมด สำหรับทุกiจะอยู่ในระดับk แรก

การสร้างฮีป KD จาก รายการ nรายการใช้ เวลา O(n)การดำเนินการต่อไปนี้ได้รับการสนับสนุน:

• แทรกรายการใหม่ในเวลาO(log n)
• ดึงข้อมูลรายการที่มีคีย์ขั้นต่ำในมิติใดก็ได้ในเวลาคงที่
• ลบรายการที่มีคีย์ต่ำสุดในมิติใดก็ได้ในเวลาO(log n)
• ลบหรือแก้ไขรายการใดๆ ในฮีปได้ในเวลาO(log n)โดยสมมติว่าทราบตำแหน่งของรายการนั้นในฮีปแล้ว

ที่สำคัญคือ ค่าคงที่ที่ซ่อนอยู่ในการดำเนินการเหล่านี้มีขนาดใหญ่มากในเชิงเลขชี้กำลังเมื่อเทียบกับค่าอื่น${\displaystyle k}$จำนวนมิติมีมาก ดังนั้นฮีป KD จึงไม่เหมาะสมสำหรับการใช้งานที่มีมิติจำนวนมาก