HEAP SORT

HEAP SORT

   การเรียงข้อมูลโดยอาศัยโครงสร้าง Heap เป็นการเรียงข้อมูลแบบที่ดีที่สุด เพราะเป็น อัลกอริทึมที่ประกันได้ว่าเวลาที่ใช้ไม่ว่าในกรณีใดจะเป็น O(log 2 n) เสมอ

โครงสร้าง Heap      heap เป็นต้นไม้ไบนารีที่มีคุณสมบัติว่าโหนดใด ๆ ในต้นไม้นั้นจะมีค่าคีย์ใหญ่กว่าค่าคีย์ที่อยู่ใน left son และ right son ของมัน (ถ้าโหนดนั้นมีลูก) ตัวอย่างดังรูป (ก) เป็น heap ส่วนรูป (ข) ไม่ใช่ heap

รูป การเปรียบเทียบระหว่างโครงสร้าง Heap กับโครงสร้างอื่น 

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


การสร้างโครงสร้าง Heap จากชุดอินพุต อาร์เรย์ใด ๆ สามารถถูกตีความเป็นต้นไม้ไบนารีได้ เช่น อาร์เรย์ที่มีค่าดังนี้

ความสัมพันธ์ระหว่างโครงสร้างอาร์เรย์และโครงสร้าง Heap จะมีรูปเป็นต้นไม้ไบนารีดังรูป

รูปต้นไม้ไบนารีของอาร์เรย์

การสร้าง Heap จะสร้างจากค่าอาร์เรย์ที่อ่านเข้ามาทีละค่าโดยจะสร้าง heap ขนาดที่มี I -1 โหนด เมื่อรับอีกโหนดเข้ามาก็จะได้ heap ที่มีขนาด I ทำเรื่อย ๆ จนได้ heap ขนาด n การอินพุตค่าใหม่เข้าไปใน heap ให้ถูกตำแหน่งค่าตามในต้นไม้ไบนารี หลักการมีดังนี้ (ให้ I เป็นพอยน์เตอร์ชี้ไปยังโหนด Knew)
ขั้นที่ 1 ให้เปรียบเทียบโหนดที่เข้าใหม่กับโหนดที่เป็นพ่อ
IF Knew > K FATHER THEN แลกที่กัน เลื่อน I ไปชี้ยังตำแหน่ง FATHER (นั่นคือ I ติดตาม Knew ขึ้นไป)
ขั้นที่ 2 ทำขั้นที่ 1 เรื่อย ๆ จนทำไม่ได้

                    ต้นไม้ที่เห็นระหว่างการสร้าง heap นั้น เป็นการตีความข้อมูลในอาร์เรย์ ส่วนความสัมพันธ์ระหว่างพ่อ - ลูก เป็นแบบที่กล่าวมาแล้วข้างต้น หลังจากที่ข้อมูลเรียงในรูปโครงสร้าง heap แล้ว เราจะเอาเอาต์พุตค่ารูตโหนดซึ่งอยุ่ที่ตำแหน่งที่ 1 ในอาร์เรย์ การเอาต์พุตเราจะให้ค่าA(1) แลกที่กับค่าสุดท้ายของอาร์เรย์ A(8) การแทนในรูปต้นไม้ ค่าที่เอาต์พุตไปแล้วจะแทนโดยโหนดสี่เหลี่ยม ต้นไม้ที่ได้ (ไม่นับโหนดสี่เหลี่ยม) ไม่เป็นโครงสร้าง heap จากนี้ต่อไปเราต้องใช้อัลกอริทึมปรับค่าคีย์ต่าง ๆ ในต้นไม้ให้คุณสมบัติ heap การปรับต้นไม้ที่ได้จากการแลกค่าให้มีคุณสมบัติ Heap การปรับแต่งทำได้โดยเลื่อนค่าที่รูตโหนดจากบนลงมาล่าง ดังนี้
ขั้นที่ 1 ให้ตั้งค่าพอยน์เตอร์ I ชี้ไปยังรูตโหนด
ขั้นที่ 2 ให้เลือกค่าที่ใหญ่ที่สุดระหว่าง left son และ right son ของโหนด I เป็นค่าที่เลื่อนมาอยู่ที่ตำแหน่ง I ส่วนค่าคีย์ที่ตำแหน่ง I ก็เลื่อนไปอยู่ที่ตำแหน่ง left son และ right son ของมันที่มีค่าใหญ่กว่า จากนั้นเลื่อนพอยน์เตอร์ I มาอยู่ที่ตำแหน่งใหม่นี้
ขั้นที่ 3 ทำขั้นที่ 2 จนกว่าจะทำไม่ได้

รูปการปรับต้นไม้ให้มีคุณสมบัติ Heap

แสดงถึงการเลื่อนค่า 22 ลงไปยังตำแหน่งถูกต้องของมัน เพื่อที่ทำต้นไม้ที่ได้เป็น heap เมื่อต้นไม้เป็นไปตามรูป (ค) ต้นไม้นั้นจะเป็น heap ซึ่งมีค่าสูงสุด 42 อยู่ที่รูตโหนด เราจะเอาต์พุต 42 ไปอยู่ที่ตำแหน่งสุดท้ายของอาร์เรย์ (ตำแหน่งก่อนค่า 90 ไป 1 ตำแหน่ง) ดังรูป (ก) ส่วนค่าที่อยู่ที่ตำแหน่งนั้น (ค่า 27) ก็ไปอยู่ที่ตำแหน่ง A(1) หรือรูตโหนด จากนั้นก็เริ่มต้นปรับแต่งต้นไม้ใหม่ให้เป็น heap ซึ่งเริ่มโดยตั้งค่า I ชี้ไปยังรูตโหน

 ประเภทของ Heap จะมีอยู่ 2 ประเภท คือ

          1. Max heap คือ ประเภทของโหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่าน้อยกว่าหรือเท่ากับข้อมูลใน โหนดพ่อโดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่ามากที่สุด

          2. Min heap คือ โหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่ามากกว่าหรือเท่ากับข้อมูลในโหนดพ่อแม่ โดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่าน้อยที่สุด

 เงื่อนไขของการแตกกิ่งก้านสาขาของโหนด คือ

          1. ทุกระดับชั้นของ heap จะแตกสาขาออกได้สองทางคือ ซ้ายและขวา การแตกโหนดจะแตกจากทางซ้ายก่อน และต้องมีโหนดในระดับรูตโหนดครบ 2 ด้านก่อนจึงจะแตกโหนดต่อไปในระดับล่างได้

          2. ค่าของโหนดที่เป็นรูตโหนดของ heap จะเป็นโหนดที่มีค่าใหญ่กว่าโหนดตัวล่าง

การเพิ่ม (Insert) โหนดเข้าไปใน Heap

          1. ถ้าโหนดที่เพิ่มเข้าไปใน heap ขณะไม่มีข้อมูลอยู่ใน heap ให้เก็บข้อมูลโหนดนั้นไว้ในตำแหน่งแรกของอาร์เรย์ที่ว่าง         
          2. ถ้าโหนดถูกเพิ่มขณะ heap มีข้อมูลหรือโหนดอยู่แล้ว การเพิ่มโหนดใหม่ใน heap  ให้ถือว่าโหนดนั้นๆเป็น Leaf  Node โดยเพิ่มโหนดในอาร์เรย์ตำแหน่งแรกที่ว่าง
           3.  ทำการเปรียบเทียบค่าโหนดใหม่กับโหนดพ่อแม่
                3.1 กรณี Max heap ถ้าโหนดใหม่ที่เพิ่มมีค่ามากกว่าโหนดพ่อ ให้สลับค่าระหว่างโหนดใหม่กับโหนดพ่อ
3.2 กรณี Min heap ถ้าโหนดใหม่ที่เพิ่มมีค่าน้อยกว่าโหนดพ่อ ให้สลับค่าระหว่างโหนดใหม่กับโหนดพ่อ
             3.3 กรณีโหนดที่เพิ่มมีค่าน้อยกว่าโหนดพ่อแม่ใน Max heap หรือมีค่ามากกว่าโหนดพ่อแม่ Min heap ให้ถือว่าโหนดนั้นเป็น Leaf Node
          4. ทำซ้ำข้อที่ 3 จนกว่าจะถึงรูตโหนดหรือไม่มีการสลับค่าระหว่างโหนดที่เพิ่มใหม่กับโหนดพ่อ

การลบ (Delete) โหนดออกจาก heap
                การลบ (Delete) โหนดออกจาก heap ต่างจากโครงสร้างแบบต้นไม้อื่นๆ โดยสามารถลบโหนดตามต้องการแต่การลบโหนดของ heap ทำได้เฉพาะโหนดที่มีค่ามากสุดในกรณี Max heap และค่าน้อยสุดใน Min heapรายละเอียดของการลบโหนดออกจาก heap มีดังนี้

          1. ลบโหนดที่มีข้อมูลที่มีค่ามากสุดใน Max heap หรือโหนดที่มีข้อมูลที่มีค่าน้อยที่สุดใน Min heap (รูตโหนด) ผลการลบเกิดตำแหน่งว่างที่ตำแหน่งแรกในอาร์เรย์

          2. ขอยืมข้อมูลจากโหนดลูกของโหนดที่ไม่มีข้อมูล โดยนำข้อมูลที่มีค่ามากมาใส่ในโหนดพ่อ จะเกิดช่องว่างที่ตำแหน่งโหนดลูกแทน

          3. ซ้ำข้อ 2 จนโหนดลูกที่ถูกขอยืมเป็น Leaf Node

        4. ถ้า Leaf Node ที่ถูกยืมไม่เป็นโหนดสุดท้ายของ heap ให้ย้ายข้อมูลจากโหนดสุดท้ายมายังโหนดดังกล่าว

 การสร้าง Heap

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

 ตัวอย่าง

ข้อมูลเริ่มต้นของฮีพ

1. สลับค่าโหนดราก คือ 100 กับค่าโหนดสุดท้ายคือ 7   

2. สลับ 36 กับ 2

      

3. สลับ 25 กับ 1

         

4. สลับ 19 กับ 2

        

5. สลับ 17 กับ 2

      

6. สลับ 7 กับ 1

      

  7. สลับ 3 กับ 2

      

8. สลับ 2 กับ 1

เหลือโหนดเดียวไม่ต้องปรับฮีพ

สิ้นสุดการทำงานข้อมูลเรียงลำดับแล้ว

  วิธีการเรียงลำดับแบบฮีพ โดยแทนฮีพพด้วย Array แสดงในรูป

	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
ฮีพเริ่มต้น	100	19	36	17	3	25	1	2	7
1. สลับ 100 กับ 7	7	19	36	17	3	25	1	2	100
ปรับฮีพ	36	19	25	17	3	7	1	2	100
2. สลับ 36 กับ 2	2	19	25	17	3	7	1	36	100
ปรับฮีพ	25	19	7	17	3	2	1	36	100
3. สลับ 25 กับ 1	1	19	7	17	3	2	25	36	100
ปรับฮีพ	19	17	7	1	3	2	25	36	100
4. สลับ 19 กับ 2	2	17	7	1	3	19	25	36	100
ปรับฮีพ	17	3	7	1	2	19	25	36	100
5. สลับ 17 กับ 2	2	3	7	1	17	19	25	36	100
ปรับฮีพ	7	3	2	1	17	19	25	36	100
6. สลับ 7 กับ 1	1	3	2	7	17	19	25	36	100
ปรับฮีพ	3	1	2	7	17	19	25	36	100
7. สลับ 3 กับ 2	2	1	3	7	17	19	25	36	100
ปรับฮีพ	2	1	3	7	17	19	25	36	100
8. สลับ 2 กับ 1	1	2	3	7	17	19	25	36	100
ปรับฮีพ	1	2	3	7	17	19	25	36	100
สิ้นสุดการเรียงลำดับ	1	2	3	7	17	19	25	36	100