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