Problem statement
หาองค์ประกอบที่มีค่าน้อยที่สุดใน Max Heap
พิจารณา Max Heap ด้านล่าง
ใน Max Heap ค่าของโหนดราก (root) จะมากกว่าลูกเสมอ ด้วยคุณสมบัตินี้ เราสรุปได้ว่าค่าน้อยที่สุดจะอยู่ที่ใบ (leaf nodes) หาก heap มี n โหนด จะมีใบ ceil(n/2) ใบ
Max Heap เป็น complete binary tree จึงสามารถแทนด้วยอาร์เรย์ ใน heap แบบนี้ ใบแรกจะอยู่หลัง index floor(n/2) ในตัวอย่าง ใบแรกอยู่ที่ index 5
อัลกอริทึม
เราสามารถใช้อัลกอริทึมด้านล่างเพื่อหาค่าต่ำสุดใน Max Heap −
1. หาใบแรกใน heap และถือค่านั้นเป็น min 2. วนลูปใบที่เหลือและอัปเดต min หากพบใบที่มีค่าน้อยกว่า
ตัวอย่าง
#include <iostream> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int getMinElement(int *heap, int n){ int minElement = heap[n / 2]; for (int i = n / 2 + 1; i < n; ++i) { minElement = min(minElement, heap[i]); } return minElement; } int main(){ int heap[] = {120, 90, 100, 70, 75, 80, 60, 25, 40, 35}; cout << "Min value: " << getMinElement(heap, SIZE(heap)) << "\n"; return 0; }ผลลัพธ์
When you compile and execute the above program. It generates the following output −
Min value: 25
