Build Heap ด้วยการค่อย ๆ เพิ่ม
โดยทั่วไปเราสร้างฮีป (binary heap) ด้วยการค่อย ๆ ปรับฮีปจากปมในต้นไม้ระดับล่างขึ้นบน
แต่ถ้ามาคิดแบบตรงไปตรงมา เราสามารถสร้างฮีปได้ด้วยการค่อย ๆ "เพิ่ม" ข้อมูล การทดลองนี้จะค่อย ๆ เพิ่ม แล้วดูสิว่า ได้ผลอย่างไรบ้าง
สิ่งที่น่าสนใจคือ ทำไมเขาถึงใช้วิธีค่อย ๆ ปรับกัน ทั้ง ๆ ที่ถ้าดูจากวงวนการเพิ่ม กับวงวนการปรับจะพบว่า การเพิ่มเปรียบเทียบแค่ครั้งเดียวต่อรอบ
แต่การปรับฮีปต้องเปรียบเทียบข้อมูลสองครั้งต่อรอบ
การทดลองสร้างฮีปข้างล่างนี้ (ทดลองกับข้อมูลเริ่มต้นสามแบบ) เรานำจำนวนครั้งทั้งหมดของการเปรียบเทียบข้อมูลในต้นไม้ มาวาดกราฟเส้นให้ดู
แล้วหารด้วย n (ปริมาณข้อมูล) ดูสิว่าเป็นกราปแสดงค่าคงตัวหรือไม่ (ดูเองครับ)
และลองดูว่า ข้อมูลเริ่มต้นแบบใดเปรียบเทียบข้อมูลเป็นจำนวนมากสุด
และอย่าลิมลองเปรียบเทียบผลกับการสร้างฮีปด้วยการค่อย ๆ ปรับ
(อ้อ เน้นอีกครั้งว่า ผลการทดลองข้างล่างนี้ เรานำจำนวนการเปรียบเทียบหารด้วย n นะครับ)
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
ข้อมูลเรียงลำดับแล้ว
ข้อมูลเรียงกลับลำดับ
ข้อมูลสุ่ม
สมชาย ประสิทธิ์จูตระกูล