ฮีปต่ำสุด-สูงสุดที่สมมาตร (SMMH) ถูกกำหนดให้เป็นทรีไบนารีที่สมบูรณ์ซึ่งแต่ละโหนดยกเว้นรูทมีองค์ประกอบเดียว รูทของ SMMH ว่างเปล่า และจำนวนโหนดทั้งหมดใน SMMH คือ m + 1 โดยที่ m คือจำนวนขององค์ประกอบ
ให้ y เป็นโหนดใดๆ ของ SMMH ให้องค์ประกอบ (y) เป็นองค์ประกอบในทรีย่อยที่รูทที่ y แต่ไม่รวมองค์ประกอบ (ถ้ามี) ใน y สมมติว่าองค์ประกอบ (y) j=∅ y มีคุณสมบัติดังต่อไปนี้:
- ลูกด้านซ้ายของ y มีองค์ประกอบขั้นต่ำในองค์ประกอบ (y)
- ลูกที่ถูกต้องของ y (ถ้ามี) มีองค์ประกอบสูงสุดในองค์ประกอบ (y)
รูปที่ 1 แสดงตัวอย่าง SMMH ที่มี 12 องค์ประกอบ
เมื่อ y หมายถึงโหนดที่มี 81 องค์ประกอบ (y) ={7, 15, 31, 41}; ลูกด้านซ้ายของ y มีองค์ประกอบขั้นต่ำ 6 ในองค์ประกอบ (y); และลูกที่ถูกต้องของ y มีองค์ประกอบสูงสุด 41 ในองค์ประกอบ (y) เราอาจตรวจสอบได้ว่าทุกโหนด y ของ SMMH นี้มีคุณสมบัติตรงตามที่ระบุ
เนื่องจาก SMMH ถูกแสดงเป็นไบนารีทรีแบบสมบูรณ์ จึงถูกจัดเก็บเป็นโครงสร้างข้อมูลโดยปริยายซึ่งนำการแมปมาตรฐานของไบนารีทรีทั้งหมดไปใช้กับอาร์เรย์ เมื่อ m =1 อิลิเมนต์ต่ำสุดและสูงสุดจะเท่ากันและอยู่ในลูกด้านซ้ายของรูทของ SMMH
เมื่อ m> 1 อิลิเมนต์ต่ำสุดจะอยู่ที่ชายด์ด้านซ้ายของรูท และค่าสูงสุดจะอยู่ที่ชายด์ด้านขวาของรูท ดังนั้นการดำเนินการ getMin และ getMax จึงใช้เวลา O(1)
เป็นเรื่องง่ายที่จะเห็นว่าไบนารีทรีแบบสมบูรณ์ m + 1 โหนดพร้อมรูทว่างและองค์ประกอบหนึ่งองค์ประกอบในทุกโหนดคือ SMMH หากสิ่งต่อไปนี้เป็นจริง -
A1 − สำหรับทุกโหนด y ที่มีพี่น้องที่ถูกต้อง องค์ประกอบใน y จะน้อยกว่าหรือเท่ากับที่ในพี่น้องที่ถูกต้องของ y
A2 - สำหรับทุกโหนด y ที่มีปู่ย่าตายาย องค์ประกอบในลูกด้านซ้ายของปู่ย่าตายายจะน้อยกว่าหรือเท่ากับสิ่งนั้นใน y
A3 - สำหรับทุกโหนด y ที่มีปู่ย่าตายาย องค์ประกอบในลูกที่ถูกต้องของปู่ย่าตายายจะมากกว่าหรือเท่ากับสิ่งนั้นใน y
ขอให้สังเกตว่าถ้าคุณสมบัติ A1 เป็นที่พอใจที่โหนด y ดังนั้นอย่างน้อยหนึ่งใน A2 และ A3 อาจถูกละเมิดที่ y การใช้คุณสมบัติ A1 ถึง A3 เราไปถึงอัลกอริทึมอย่างง่ายเพื่อแทรกและลบองค์ประกอบ อัลกอริธึมเหล่านี้เป็นการปรับอย่างง่ายของอัลกอริทึมที่สอดคล้องกันสำหรับฮีปต่ำสุดและสูงสุด ความซับซ้อนคือ O(log m)
ที่นี่ เราระบุการดำเนินการแทรก สมมติว่าเราต้องการแทรก 3 ลงใน SMMH ของรูปที่ 1 เนื่องจาก SMMH เป็นไบนารีทรีที่สมบูรณ์ เราจึงต้องเพิ่มโหนดใหม่ให้กับ SMMH ในตำแหน่งที่แสดงในรูปที่ 2 โหนดใหม่มีป้ายกำกับว่า B.
ในตัวอย่างของเรา B จะแสดงถึงโหนดที่ว่างเปล่า ตอนนี้ 3 ถูกแทรกที่โหนด B.
