Heap Tree และการจัดเรียงข้อมูลใน Heap

Heap Tree เป็นโครงสร้างข้อมูลแบบต้นไม้ (Tree) ในบทความนี้จะเป็นการอ้างอิงเนื้อหาจากความรู้เรื่องโครงสร้างต้นไม้ (Tree) ซึ่งผมได้อธิบายเบื้องต้นไว้ในบทความ ทำความรู้จักกับโครงสร้างข้อมูลแบบต้นไม้ (Tree) โครงสร้าง Heap Tree เป็นโครงสร้างที่สามารถจัดเรียงข้อมูล และค้นหาข้อมูลได้มีประสิทธิภาพ ดีสุดที่ O(n log n) เฉลี่ย O(n log n) และแย่สุดที่ O(n log n)  ซึ่งมีประสิทธิภาพสูงกว่า Bubble Sort และ Selection Sort เป็นอย่างมาก

Tree เป็นแนวคิดโครงสร้างที่มนุษย์ออกแบบขึ้นสำหรับใช้กับข้อมูล โดยลอกเลียนแบบมาจากโครงสร้างต้นไม้ในชีวิตจริง เป็นการมองข้อมูลใน Array ธรรมดาให้มีแนวคิดและโครงสร้างขึ้นมา และสามารถจัดการกับข้อมูลใน Array ได้แบบมีประสิทธิภาพ โดยที่ Array ก็ยังเป็น Array ธรรมดาเช่นเดิม

Heap Tree

Max Heap คือโครงสร้างที่ Root Node มีค่ามากที่สุด ส่วน Min Heap คือโครงสร้างที่ Root Node มีค่าน้อยที่สุด

การทำให้ Heap เป็น Max Heap มีขั้นตอนคือ การให้สลับให้ Parents Node มีค่ามากกว่า Child Node ไปเรื่อยๆ

เมื่อได้ Max Heap Tree แล้ว ให้สลับ Root Node กับ Leaf Node ตัวสุดท้าย จากนั้นเราจะล็อคมันไว้ (สัญลักษณ์สีเขียว) โดยเราจะไม่ได้ไปยุ่งกับมัน เนื่องจากตัวมันมากที่สุด และอยู่ถูกตำแหน่งแล้ว

เมื่อได้ตัวที่มากที่สุด แล้วสลับที่แล้ว เราจะเริ่มการสร้าง Max Heap ใหม่ โดยการสลับ Child Node ที่มากกว่า Parent Node และนำ Parent Node มาสลับกับ  Root Node เพื่อให้ตัวที่มีค่ามากที่สุดอยู่ที่ Root Node เสมอ

จากนั้นก็ทำเช่นเดิม คือการนำ Root Node มาสลับ กับ Leaf Node สุดท้าย โดยเราจะไม่ไปยุ่งกับ ตัวมากสุดก่อนหน้าที่เราได้ทำการล็อคไว้

จากนั้นก็สร้าง Max Heap และย้าย Root Node ซ้ำไปเรื่อยๆ จนกว่าตัวเลขทุกตัวจะเรียงกันถูกต้อง 

อ้างอิง: www.javatpoint.com/heap-sort