Binary Heap คืออะไร

สวัสดีครับวันนี้เราจะมาพูดกันถึง binary heap นะครับ สำหรับ binary heap นั้นคือโครงสร้างข้อมูลในแบบหนึ่ง ซึ่งโครงสร้างข้อมูลแบบนี้มีข้อดีคือทำงานได้คอนข้างเร็วกว่าการใช้ vector หรือการเก็บแบบ array ยาวๆปกติ การใช้ vector หรือเก็บ array ยาวแบบปกติจะใช้เวลาในการจัดการข้อมูลค่อนข้างมากเพราะเมื่อไรที่ array ที่เราจองเต็มแล้วเราต้องสร้าง array ใหม่ที่มีขนาดใหญ่กว่าเดิมมาเพื่อเก็บข้อมูลใหม่ และยังต้องก๊อปข้อมูลจาก array เดิมไปสู่ array ใหม่อีกด้วย แล้วเราจะเจอ binary heap ที่ไหนบ้างละนั้นก็คือ priority_queue นั้นเอง

แผนภาพด้านบนเรียกว่า binary heap นะครับ ไม่ต้องสนใจค่าของตัวเลขที่อยู่ในนั้นเราใส่ไว้แค่บอกว่าอันไหนเป็นจุดที่เท่าไรแค่นั้นเอง55555555

ส่วนประกอบของ binary heap มี 3 ส่วนคือ root parent และ child โดย root คือ รากด้านบนเบอร์ 10 นั้นเอง ส่วน parent จะมีหลายอัน เช่น 8 เป็น parent ของ 4 และ 5,9 เป็น parent ของ 6,7 ในทางกลับกัน 4,5 6,7 ก็เป็น child ของ 8 และ 9 ด้วยตามลำดับ วิธีการเติม binary heap เราจะเริ่มเติมจากทางด้านซ้ายก่อนและค่อยเติมเรื่อยๆจนเต็ม(1,2,3) ละค่อยขึ้นบรรทัดใหม่หรือขึ้นอีกรุ่นนึง

ที่มา : https://www.google.co.th/url?sa=i&rct=j&q=&esrc=s&source=images&cd=&cad=rja&uact=8&ved=2ahUKEwjW0cPL6q7eAhWJN48KHS35DhMQjRx6BAgBEAU&url=http%3A%2F%2Fwww.cse.hut.fi%2Fen%2Fresearch%2FSVG%2FTRAKLA2%2Ftutorials%2Fheap_tutorial%2Ftaulukkona.html&psig=AOvVaw0ncNmjMwhWgY0Tg_BDJ5-W&ust=1541011789629547

ขอก๊อปรูปมาจากอินเตอร์เน็ตเพื่อประกอบการอธิบายนะครับ เนื่องจากทำภาพไม่ไหวจริงๆ อย่าที่เราเห็นนะว่าโครงสร้างของ binary heap สุดท้ายก็ต้องมาถูกจัดโครงสร้างเป็น array เพียงแต่ว่าการจัดเก็บมันจะแตกต่างจากการจัดเก็ของ array ปกติ โดย child ของ parent จะเก็บที่ 2n,2n+1 เมื่อเป็นลูกทางด้านซ้ายและทางด้านขวาตามลำดับ ทำให้เวลาเรา เพิ่มหรือลด ข้อมูลจะทำได้เร็วกว่าการทำงานของ array และ vector ปกติ ที่นี้ทุกครั้งที่เราเพิ่มข้อมูลเราต้องเพิ่มที่ใบมันคือ node ล่างสุด ปัญหาคือมันจะเรียงตามลำดับได้อย่างไรถ้าตัวที่เราเพิ่มไม่ได้เป็นเป็นตามที่เราต้องการ เราจึงมีกระบวนการที่เรียกว่า fix up นั้นคือการที่เราจะเปรียบเทียบกับ parent ว่าใครมากกว่ากัน แต่ก่อนไปเทียบกับ parent เราต้องเทียบกับลูกด้วยกันเองก่อน เริ่มงงละอะดิ5555555 อย่างที่ชื่อบอกอันนี้คือ binary heap นั้นหมายความว่า 1 parent มีเพียงได้แค่ 2 ลูกเท่านั้น นั่นเท่ากับว่าก่อนที่เราจะไปเทียบกับ parent เราต้องเทียบระหว่างลูกกันเองก่อนเพื่อให้ชัวว่าคนที่จะไปเทียบกับ parent จะใหญ่ที่สุดในบรรดาลูกๆที่มีเพียง 2 คน จากนั้นค่อยไปทเียบกับ parent ถ้า parent แพ้ เราก็จะสลับที่ระหว่างลูกกับ parent ไปเรื่อยจน parent ชนะหรือไปอยู่จุดบนสุดนั้นก็จะทำให้มันเรียงจากมากไปน้อยได้ตามที่เราต้องการ กระบวนการที่ว่านี้จะถูกใช้ตอนที่เรา push ข้อมูลเพิ่มเข้าไป

แต่ถ้าเราต้องการ pop ข้อมูลออกละตัว node ที่เป็นรากก็จะหายไป โดยวิธีที่ binary heap ออกแบบไว้คือเราจะเอาตัวที่เป็นใบที่มีค่าน้อยที่สุดไปแทนค่าที่ราก จากนั้นจะเปรียบเทียบลงมาเรื่อยๆจนกระทั่งพ่อแม่มีค่ามากกว่าลูก วิธีการนี้เรียกว่า fixDown ซึ่งด้วยคุณสมบัติในการออกแบบ binary heap แบบนี้ส่งผลให้การเพิ่มหรือลบข้อมูลทำได้เร็วกว่าการเก็บข้อมูลธรรมดาทั่วไปนั้นเอง

เพิ่มเติม binary heap รูปด้านบนทั้งสองลูกเรียกว่าสูง 4 นะครับ โดยประสิทธิภาพในการเพิ่มและการลดมีค่าเป็น log ฐาน 2 ของความสูงของ heap ซึ่งเราจะไปอธิบายกันอีกทีในเรื่องของ bigO น้า พบกันใหม่ครั้งหน้าครับ