priority queue

เป็น ADT ที่ใช้เก็บข้อมูล ภายใน Priority queue จะมีการเรียงข้อมูลตาม Priority จากมากไปน้อยตลอดเวลา ดังนั้นการสร้าง Priority queue นั้นจำเป็นที่จะต้องมีเกณฑ์ที่บอกว่าข้อมูลตัวใดมี Priority มากกว่าข้อมูลอีกตัวหนึ่ง เช่น หากต้องการจะให้ Priority queue ดำเนินการกับข้อมูลที่มีค่าน้อยก่อนค่าที่มีค่ามาก นั่นคือเป็นการกำหนดให้ Priority แทนการ "น้อยกว่า" เมื่อใส่จำนวน 1 6 3 4 8 ลงใน Priority queue นี้ตามลำดับ และนำข้อมูลออกจาก Priority queue เรื่อยๆ จะได้ว่าข้อมูลที่ออกมาคือ 1 3 4 6 8

operation พื้นฐาน

insert

เป็นการเพิ่มข้อมูลลงไปใน Priority queue

get

เป็นการดูว่าข้อมูลที่มี Priority มากสุดมีค่าเท่าใด

remove

เป็นการลบข้อมูลที่มี Priority มากสุดออกไป

สังเกตว่าการดำเนินการต่างๆนอกจากการเพิ่มข้อมูลนั้น เราจะดำเนินการกับปลายฝั่งที่มี Priority สูงสุดเสมอ

การ implement

เช่นเดียวกันกับ ADT อื่นๆ การ implement Priority queue สามารถทำได้หลายแบบ ซึ่งแต่ละแบบก็จะเหมาะกับสถานการณ์ต่างๆกันไป
ขอใช้รูปแบบ $<O(f(n)),O(g(n)),O(h(n))>$ ในการอธิบายว่าการ implement นี้ insert ภายในเวลา $O(f(n))$ , get ภายในเวลา $O(g(n))$ และ remove ภายในเวลา $O(h(n))$

ใช้ array ธรรมดา

การใช้ array ธรรมดาก็อาจจะ implement ได้หลายแบบอีกเช่นกัน อาจจะเป็นการใส่ข้อมูลต่อๆกัน แล้วเมื่อต้องการจะหาข้อมูลที่มี Priority มากสุดก็มาไล่หา ซึ่งวิธีนี้ก็จะใช้เวลา $<O(1),O(n),O(n)>$
อีกวิธีก็อาจจะทำคล้ายๆ insertion sort คือพยายามทำให้ array เรียงตัวเองตลอดเวลา ซึ่งวิธีนี้ก็จะใช้เวลา $<O(n),O(1),O(1)>$
อย่างไรก็ตามทั้ง 2 วิธีมีเวลาในการดำเนินการกับข้อมูล $O(n)$ ซึ่งช้ามาก แต่อาจจะเหมาะกับบางสถานการณ์เช่นการหาค่าน้อยสุดในปัญหา shortest path บน Dense graph ซึ่งการใช้วิธี $<O(1),O(n),O(n)>$ จะให้ผลดีมาก

ใช้ heap

heap เป็น data structure ที่นิยมมากที่สุดในการ implement Priority queue เนื่องจากเขียนไม่ยากมากและประสิทธิภาพดีมาก
ใช้เวลา $<O(log(n)),O(1),O(log(n))>$ อ่านรายละเอียดเพิ่มเติมที่ heap

ใช้ balanced binary search tree

balanced binary search tree เป็น data structure อีกตัวที่ใช้เวลา $<O(log(n)),O(1),O(log(n))>$ มีข้อดีมากกว่า heap คือสามารถดำเนินการกับข้อมูลต่างๆที่ไม่ใช่ข้อมูลที่มากที่สุดได้ด้วย อย่างไรก็ตาม การ implement นั้นค่อนข้างจะยากและโดยปกติก็ไม่ได้มีความจำเป็นที่จะต้องใช้ความสามารถมากขนาดนั้น จึงไม่ค่อยนิยม อ่านรายละเอียดเพิ่มเติมที่ BST

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License