แถวคอยเชิงบุริมภาพ

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

วัตถุประสงค์

เพื่อให้ผู้เรียนสามารถ

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