Heap Sort Flash Animate

Heap Sort นั้นมี 2 ประเภท คือ Max Heap และ Min Heap

Max Heap เป็นการเรียงข้อมูลที่มีค่ามากสุดไปไว้้ด้านบนของฮีพ

Min Heap เป็นการเรียงข้อมูลที่มีค่าน้อยสุดไปไว้ด้านบนของฮีด

Max Heap

ตัวอย่างโจทย์

5

7

6

3

9

2

8

4

1

0

การสร้างฮีพจะอาศัยการ insert เข้าไปทีละตัวแล้วเปรียบเทียบกับโหนด parent ว่าค่านั้นๆมีค่ามากกว่าในparentหรือไม่ ถ้าใช้จะทำการสลับตำแหน่งกับ parent ขึ้นแล้ว แล้วเปรียเทียบกับparentตัวใหม่ต่อไป ดังนี้

insert 5

insert 7

เิริ่มแรกนำ 7 มาต่อโหนดสุดท้าย(ในที่นี้คือ5)(เริ่มต่อจากด้านซ้ายก่อน) จากนั้นเปรียบเทียบ 7 กับโหนดparent(ในที่นี้คือ5)ว่ามีค่ามากกว่าหรือไม่ ถ้าใช่ ให้สลับตำแหน่งกับ parent ดังรูป

insert 6

นำ 6 มาต่อ(ต่อเข้าด้านขวาเพื่อให้รูปเต็มสามเหลี่ยม) จากนั้นเปรียบเทียบ 6 กับโหนดparent(ในที่นี้คือ7)ว่ามีค่ามากกว่าหรือไม่ ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 3

นำ 3มาต่อ(ต่อเข้าด้านซ้ายเพื่อให้รูปเป็นสามเหลี่ยม) จากนั้นเปรียบเทียบ 3 กับโหนดparent(ในที่นี้คือ5)ว่ามีค่ามากกว่าหรือไม่ ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 9

นำ 9 มาต่อ(ต่อเข้าด้านขวาเพื่อให้รูปเต็มสามเหลี่ยม 3 5 9)

จากนั้นเปรียบเทียบ 9 กับโหนดparent(ในที่นี้คือ 5)ว่ามีค่ามากกว่าหรือไม่

ถ้าใช่ ให้สลับตำแหน่งกับ parent ดังรูปด้านบน

จากนั้นจึงนำ 9 ไปเปรียบเทียบกันโหนด parent ใหม่ (ในที่นี้คือ 7) ว่ามีค่ามากกว่าหรือไม่

ถ้าใช่ ให้สลับตำแหน่งกับ parent ดังรูปด้านบน

insert 2

นำ 2 มาต่อ(ต่อเข้าด้านซ้ายของ 6 เพื่อให้รูปเป็นสามเหลี่ยม) จากนั้นเปรียบเทียบ 2 กับโหนดparent(ในที่นี้คือ 6)ว่ามีค่ามากกว่าหรือไม่ ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 8

นำ 8 มาต่อ(ต่อเข้าด้านขวาเพื่อให้รูปเต็มสามเหลี่ยม 2 8 6)

จากนั้นเปรียบเทียบ 8 กับโหนดparent(ในที่นี้คือ 6)ว่ามีค่ามากกว่าหรือไม่

ถ้าใช่ ให้สลับตำแหน่งกับ parent ดังรูปด้านบน

จากนั้นจึงนำ 8 ไปเปรียบเทียบกันโหนด parent ใหม่ (ในที่นี้คือ 9) ว่ามีค่ามากกว่าหรือไม่

ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 4

นำ 4 มาต่อ(ต่อเข้าด้านซ้ายเพื่อให้เป็นรูปสามเหลี่ยม)

จากนั้นเปรียบเทียบ 4 กับโหนดparent(ในที่นี้คือ 3)ว่ามีค่ามากกว่าหรือไม่

ถ้าใช่ ให้สลับตำแหน่งกับ parent ดังรูปด้านบน

จากนั้นจึงนำ 4 ไปเปรียบเทียบกันโหนด parent ใหม่ (ในที่นี้คือ 7) ว่ามีค่ามากกว่าหรือไม่

ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 1

นำ 1 มาต่อ(ต่อเข้าด้านขวาเพื่อให้รูปเต็มสามเหลี่ยม 3 4 1)

จากนั้นเปรียบเทียบ 1 กับโหนดparent(ในที่นี้คือ 4)ว่ามีค่ามากกว่าหรือไม่

ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

insert 0

นำ 0 มาต่อ(ต่อเข้าด้านซ้ายเพื่อให้เป็นรูปสามเหลี่ยม)

จากนั้นเปรียบเทียบ 0 กับโหนดparent(ในที่นี้คือ 5)ว่ามีค่ามากกว่าหรือไม่

ถ้าไม่ใช่ ก็ไม่ต้องสลับตำแหน่งกับ parent ดังรูป

ส่วนการทำ Min Heap จะใช้วิธีเดียวกับ Max Heap แต่จะเปลี่ยนจากการเปรียบเทียบเอาค่ามากขึ้นเป็นเอาค่าน้อยขึ้นแทน

Delete Heap >>

Sign GuestBook