เรดิกซ์ฮีป (Radix Heap)เป็นโครงสร้างข้อมูลที่ใช้ในการดำเนินการของคิวลำดับความสำคัญแบบโมโนโทน (Monotone Priority Queue)โดยสามารถจัดการชุดขององค์ประกอบที่กำหนดคีย์ให้ เวลาในการทำงานของการดำเนินการขึ้นอยู่กับความแตกต่างระหว่างคีย์ที่ใหญ่ที่สุดและคีย์ที่เล็กที่สุด หรือค่าคงที่ โครงสร้างข้อมูลนี้ประกอบด้วยบัคเก็ต (Bucket) จำนวนมาก ซึ่งขนาดของบัคเก็ตจะเพิ่มขึ้นแบบทวีคูณ

1. คีย์ทั้งหมดเป็นจำนวนธรรมชาติ ;
2. ปุ่มสูงสุด - ปุ่มต่ำสุด${\displaystyle \leq }$C สำหรับค่าคงที่ C;
3. การดำเนินการ extract -minเป็นแบบโมโนโทนิก กล่าวคือ ค่าที่ส่งคืนโดย การเรียกใช้ extract-min ครั้งต่อๆ ไป จะเพิ่มขึ้นอย่างต่อเนื่อง

สามสาขา ที่สำคัญที่สุด ได้แก่:

1. อาร์เรย์${\displaystyle b}$ขนาด${\displaystyle B:=\lfloor log(C+1)\rfloor +1}$โดยมี 0 เป็นดัชนีต่ำสุด จะใช้เก็บกลุ่มข้อมูล (buckets);
2. อาร์เรย์${\displaystyle u}$ขนาด${\displaystyle B+1}$โดยกำหนดให้ 0 เป็นดัชนีต่ำสุด ใช้สำหรับจัดเก็บขอบเขต (ล่าง) ของกลุ่มข้อมูล
3. ${\displaystyle bNum}$ใช้ได้กับแต่ละองค์ประกอบ${\displaystyle x}$ในกองนั้นก็คือถังที่ใช้เก็บมัน

แผนภาพด้านบนแสดงโครงสร้างข้อมูล โดยมีเงื่อนไขคงที่ดังต่อไปนี้:

1. ${\displaystyle u[i]\leq }$กุญแจใน${\displaystyle b[i]<u[i+1]}$: กุญแจใน${\displaystyle b[i]}$ขึ้นหรือลงผ่านค่าใน${\displaystyle u[i+1]}$หรือ${\displaystyle u[i]}$จำกัด
2. ${\displaystyle u[0]=0,u[1]=u[0]+1,u[B]=\infty }$และ${\displaystyle 0\leq u[i+1]-u[i]\leq 2^{i-1}}$สำหรับ${\displaystyle i=1,\ldots ,B-1}$ขนาดของถังจะเพิ่มขึ้นแบบทวีคูณ

สิ่งสำคัญคือต้องสังเกตการเติบโตแบบเลขชี้กำลังของขีดจำกัด (และด้วยเหตุนี้ช่วงที่ถังบรรจุได้) ด้วยวิธีนี้ การพึ่งพาแบบลอการิทึมของปริมาณสนามจะมีค่าเท่ากับ C ซึ่งเป็นความแตกต่างสูงสุดระหว่างค่าสำคัญสองค่า

ในระหว่างการเริ่มต้นระบบจะมีการสร้างถังว่างเปล่าและขอบเขตล่างขึ้นมา${\displaystyle u}$ถูกสร้างขึ้น (ตามเงื่อนไขคงที่ข้อที่ 2); เวลาในการทำงาน${\displaystyle O(B)}$.

ระหว่างการแทรกองค์ประกอบใหม่${\displaystyle x}$เคลื่อนที่เชิงเส้นจากขวาไปซ้ายผ่านถังและองค์ประกอบใหม่ด้วย${\displaystyle k(x)}$ถูกจัดเก็บไว้ในถังด้านซ้ายสำหรับสิ่งนั้น${\displaystyle u[i]\geq k(x)}$เวลาในการทำงาน${\displaystyle O(B)}$.

สำหรับdecrease-keyขั้นแรกค่าของคีย์จะถูกลดลง (โดยตรวจสอบว่าสอดคล้องกับเงื่อนไขคงที่หรือไม่) จากนั้น...${\displaystyle bNum}$ฟิลด์นี้ใช้สำหรับระบุตำแหน่งขององค์ประกอบ และจะวนซ้ำไปทางซ้ายหากจำเป็น ในลักษณะเดียวกับ การดำเนินการแทรก เวลาในการ ทำงานคือ${\displaystyle O(1)}$(คิดค่าเสื่อมราคา)

การ ดำเนินการ extract-minจะลบองค์ประกอบออกจากบัคเก็ต${\displaystyle b[0]}$และส่งคืน หากถัง${\displaystyle b[0]}$หากถังเก็บข้อมูลยังไม่ว่างเปล่า การดำเนินการจะสิ้นสุดลง แต่ถ้าหากถังเก็บข้อมูลว่างเปล่าแล้ว ระบบจะค้นหาถังเก็บข้อมูลขนาดใหญ่ถัดไปที่ไม่ว่างเปล่า โดยพิจารณาจากองค์ประกอบที่เล็กที่สุดในถังเก็บข้อมูลนั้น${\displaystyle k}$ติดตามและ${\displaystyle u[0]}$กำหนดให้เป็น k (จำเป็นต้องมีคุณสมบัติความเป็นเอกรูป) จากนั้น ตามเงื่อนไขคงที่ ขอบเขตของถังจะถูกกำหนดใหม่และองค์ประกอบจะถูกลบออก${\displaystyle b[i]}$ไปยังถังที่ก่อตัวขึ้นใหม่; เวลาในการทำงาน${\displaystyle O(1)}$(คิดค่าเสื่อมราคา)

หากแสดงผล ฟิลด์นั้น${\displaystyle bNum}$ได้รับการอัปเดตแล้ว