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

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

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

 เปรียบเทียบ heapsort กับ merge sort และ quicksort 
thumb|ตัวอย่างอัลกอริทึมจัดเรียงที่เสถียร: ในการเล่นไพ่ เมื่อไพ่ถูกจัดเรียงตามอันดับด้วยการจัดเรียงที่เสถียร ไพ่เลข 5 ทั้งสองจะต้องอยู่ในลำดับเดียวกันในผลลัพธ์ที่เรียงลำดับตามเดิม แต่เมื่อเรียงด้วยการเรียงลำดับที่ไม่เสถียร ไพ่เลข 5 ทั้งสอง อาจไปอยู่ในตำแหน่งตรงข้ามกัน หลังจากที่การเรียงลำดับสิ้นสุดลง
โดยทั่วไปในทางปฏิบัติแล้ว 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 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด
right|thumb|350x350px|ตัวอย่างฮีปซอร์ต

 การสร้างฮีป 
ฮีปสมาชิกใหม่ใส่เข้าไปในฮีปสลับ (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เรียงสมบูรณ์