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