องค์ประกอบขั้นต่ำในฮีปสูงสุดใน C ++

คำชี้แจงปัญหา

ค้นหาองค์ประกอบที่มีค่าน้อยที่สุดในฮีปสูงสุด

ให้เราพิจารณาด้านล่างฮีปสูงสุด

ในค่าฮีปสูงสุดของโหนดรูทจะมากกว่าค่าลูกเสมอ เนื่องจากคุณสมบัตินี้ เราสามารถสรุปได้ว่าค่านั้นจะมีอยู่ในโหนดปลายสุดอันใดอันหนึ่ง ถ้าฮีปมี n โหนด ก็จะมี ceil(n/2) เหลือ

Max heap เป็นไบนารีทรีที่สมบูรณ์ จึงสามารถแสดงในอาร์เรย์ได้ ในกองดังกล่าว ใบไม้แรกจะอยู่หลังดัชนีพื้น (n/2) ในตัวอย่างของเรา การลาครั้งแรกจะแสดงที่ดัชนี 5

อัลกอริทึม

เราสามารถใช้อัลกอริธึมด้านล่างเพื่อค้นหาค่าต่ำสุดในฮีปสูงสุด -

<ก่อน>1. ค้นหา Leaf แรกใน heap และพิจารณาค่าเป็น min2 ทำซ้ำใบที่เหลือทั้งหมดและอัปเดตค่าขั้นต่ำหากพบใบไม้ที่มีค่าน้อยกว่า

ตัวอย่าง

#include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้ namespace std;int getMinElement(int *heap, int n){ int minElement =heap[n / 2]; สำหรับ (int i =n / 2 + 1; i  ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ค่าต่ำสุด:25