ฮีปซอร์ต

ในทางวิทยาการคอมพิวเตอร์ ฮีปซอร์ต หรือ อัลกอริทึมจัดเรียงแบบฮีป () คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบฮีป (heap) เป็นหลักในการจัดเรียง

ฮีปซอร์ตและโครงสร้างข้อมูลฮีป คิดค้นขึ้นโดย จอห์น (วิลเลียม โจเซฟ) วิลเลียมส์ ในปี ค.ศ. 1964

ฮีปซอร์ตจัดเป็นหนึ่งในกลุ่มซีเล็กชันซอร์ต (selection sort) กล่าวคือ อัลกอริทึมจะนำตัวที่มีค่าสูงที่สุดในอาร์เรย์ไปไว้ข้างหลังสุด และตัวที่สูงสุดอันดับที่สองตามมา จนถึงตัวสุดท้าย โดยใช้วิธีการสลับ (swaping) แต่ฮีปซอร์ตมีประสิทธิภาพสูงกว่าซีเล็กชันซอร์ตมากกว่าหลายเท่า

 เปรียบเทียบ heapsort กับ merge sort และ quicksort 
โดยทั่วไปในทางปฏิบัติแล้ว heapsort จะช้ากว่า merge sort และ quicksort และถือเป็นอัลกอริทึมที่ไม่เสถียร (unstable algorithm) กล่าวคือ heapsort จะไม่ทำการรักษาตำแหน่งของเรคคอร์ดในอาร์เรย์ในกรณีที่ตำแหน่งสองตำแหน่งขึ้นไปนั้น มีค่า (value/key) ที่เท่ากัน

อย่างไรก็ดี heapsort ไม่จำเป็นต้องใช้พื้นที่ในการเก็บข้อมูล (memory space) เหมือนกับ merge sort และเวลารันในกรณีที่แย่ที่สุดของ heapsort คือ Θ(nlogn) ทำให้เร็วกว่า quicksort ซึ่งมีเวลารันในกรณีที่แย่ที่สุดคือ O(n2)

 ตัวอย่าง 
ให้ { 6, 5, 3, 1, 8, 7, 2, 4 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด

 การสร้างฮีป 
ฮีปสมาชิกใหม่ใส่เข้าไปในฮีปสลับ (swap) สมาชิกNULL (ว่างเปล่า)6656, 536, 5, 316, 5, 3, 186, 5, 3, 1, 85, 86, 8, 3, 1, 56, 88, 6, 3, 1, 578, 6, 3, 1, 5, 73, 78, 6, 7, 1, 5, 328, 6, 7, 1, 5, 3, 248, 6, 7, 1, 5, 3, 2, 41, 48, 6, 7, 4, 5, 3, 2, 1

 การเรียง 
ฮีปสลับ (swap) สมาชิกลบ (delete) สมาชิกอาร์เรย์ที่จัดเรียงแล้วข้อมูล8, 6, 7, 4, 5, 3, 2, 18, 1สลับ 8 และ 1 เพื่อลบ 8 จากฮีป1, 6, 7, 4, 5, 3, 2, 88ลบ 8 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว1, 6, 7, 4, 5, 3, 21, 78สลับ 1 และ 7 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป7, 6, 1, 4, 5, 3, 21, 38สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป7, 6, 3, 4, 5, 1, 27, 28สลับ 7 และ 2 เพื่อลบ 7 จากฮีป2, 6, 3, 4, 5, 1, 778ลบ 7 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว2, 6, 3, 4, 5, 12, 67, 8สลับ 2 และ 6 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป6, 2, 3, 4, 5, 12, 57, 8สลับ 2 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป6, 5, 3, 4, 2, 16, 17, 8สลับ 6 และ 1 เพื่อลบ 6 จากฮีป1, 5, 3, 4, 2, 667, 8ลบ 6 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว1, 5, 3, 4, 21, 56, 7, 8สลับ 1 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป5, 1, 3, 4, 21, 46, 7, 8สลับ 1 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป5, 4, 3, 1, 25, 26, 7, 8สลับ 5 และ 2 เพื่อลบ 5 จากฮีป2, 4, 3, 1, 556, 7, 8ลบ 5 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว2, 4, 3, 12, 45, 6, 7, 8สลับ 2 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป4, 2, 3, 14, 15, 6, 7, 8สลับ 4 และ 1 เพื่อลบ 4 จากฮีป1, 2, 3, 445, 6, 7, 8ลบ 4 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว1, 2, 31, 34, 5, 6, 7, 8สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป3, 2, 13, 14, 5, 6, 7, 8สลับ 3 และ 1 เพื่อลบ 3 จากฮีป1, 2, 334, 5, 6, 7, 8ลบ 3 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว1, 21, 23, 4, 5, 6, 7, 8สลับ 1 และ 2 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป2, 12, 13, 4, 5, 6, 7, 8สลับ 2 และ 1 เพื่อลบ 2 จากฮีป1, 223, 4, 5, 6, 7, 8ลบ 2 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว112, 3, 4, 5, 6, 7, 8ลบ 1 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว1, 2, 3, 4, 5, 6, 7, 8เรียงสมบูรณ์

 อ้างอิง 

 บรรณานุกรม 


 แหล่งข้อมูลอื่น 



หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ
หมวดหมู่:ฮีป (โครงสร้างข้อมูล)
หมวดหมู่:การเรียงแบบเปรียบเทียบ