แถวคอยลำดับความสำคัญ

แถวคอยลำดับความสำคัญ
ความสำคัญของลำดับ	FIFO (First In Fast Out) แต่เรียงตามลำดับความสำคัญ
การซ้ำกันของสมาชิก	อนุญาตให้ซ้ำกันได้
เวลาที่ใช้ในการเข้าถึง	ENQUEUE/DEQUEUE (เรียงตามลำดับความสำคัญ)
โครงสร้างที่นำไปใช้	ฮีป

ในแถวคอยปกติ ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่นการให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท เช่นนี้เราจะสร้าง แถวคอยลำดับความสำคัญ (อังกฤษ: Priority Queue) เป็นคิวที่ถึงแม้เข้าก่อน แต่สิ่งที่มีความสำคัญมากกว่าจะได้ออกก่อน ถ้ามีความสำคัญเท่ากัน ข้อมูลที่เข้ามาก่อนจะได้ออกก่อนเช่นเดียวกับแถวคอยปกติ

แถวคอยลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงแถวคอยได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้แถวคอยลำดับความสำคัญในการจัดการทำงาน การตรวจนับ ฯลฯ

จุดเด่น

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

บริการที่มักจะมี

• เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (enqueue)
• ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นออกมา (prioritized dequeue)
• ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)

ตัวอย่างการเขียนโปรแกรม (ภาษา C++)

#include <bits/stdc++.h>
using namespace std;    

class node{
public:
    int age;
    string name;
    node(int a, string b){
        age = a;
        name = b;
    }
};

bool operator<(const node& a, const node& b) {

    node temp1=a,temp2=b;
    if(a.age != b.age)
        return a.age > b.age;
    else{
        return temp1.name.append(temp2.name) > temp2.name.append(temp1.name);
    }
}

int main(){
    priority_queue<node> pq;
    node b(23,"Somchai");
    node a(22,"Pongsak");
    node c(22,"Manee");
    pq.push(b);
    pq.push(a);
    pq.push(c);

    int size = pq.size();
    for (int i = 0; i < size; ++i)
    {
        cout<<pq.top().age<<" "<<pq.top().name<<"\n";
        pq.pop();
    }
}

จากโปรแกรมข้างต้น เราจะทำการสร้าง แถวคอย โดยโปรแกรมมีเงื่อนไขว่า ใครที่อายุ(Age)น้อยที่สุด จะถูกเรียกชื่อก่อนเสมอ โดยหากมีหลายคนที่อายุเท่ากัน คนที่ถูกเพิ่มเข้าไปในคิวภายหลังจากถูกเรียกก่อนเสมอ

ลำดับการเพิ่มข้อมูล

1. Somchai อายุ 23 ปี >> node a(23,"Somchai");
2. Pongsak อายุ 22 ปี >> node b(22,"Pongsak");
3. Manee อายุ 22 ปี >> node c(22,"Manee");

ผลการทำงานของโปรแกรม

22 Manee

22 Pongsak

23 Somchai

จากผลการทำงานของโปรแกรมข้างต้น จะสังเกตได้ว่า ถึงแม้ Somchai จะมาก่อน แต่ว่าจะถูกเรียกท้ายสุดเพราะอายุมากที่สุด ส่วน Manee จะถูกเรียกเป็นอันดับแรก ถึงแม้ว่าจะอายุเท่ากันกับ Pongsak แต่ว่า Manee มาทีหลังสุด ดังนั้นจึงได้ความสำคัญมากกว่า Pongsak ตามหลักการของ "แถวคอยลำดับความสำคัญ (Priority queue)"

ความเร็วที่ใช้ในการทำงาน

ถึงแม้ว่าการเอาออกของข้อมูลที่สำคัญที่สุดอาจยุ่งยาก แต่ด้วยการจัดการที่เหมาะสม เราสามารถรักษาความเร็วการทำงานของแถวคอยลำดับความสำคัญไว้ที่ O (1) ได้

โครงสร้างข้อมูล

• การใช้แถวคอยธรรมดาแต่ค้นหาตัวสำคัญที่สุด วิธีนี้จะทำให้การคืนค่ารายการใช้เวลา O (1)
• การใช้แถวคอยตะกร้า (bucket queue) โดยการสร้างแถวคอยธรรมดาหลายๆแถว แต่ละแถวเก็บลำดับความสำคัญที่เท่าๆกัน และเรียงลำดับที่สำคัญมากสุดลงมา วิธีนี้จัดการยากพอสมควร
• วิธีที่นิยมที่สุดคือ ฮีป (heap) เป็นการนำแนวคิดต้นไม้ในเชิงการเรียงลำดับให้ตัวที่สำคัญที่สุดอยู่บนๆ และนำตัวบนสุดมาตอบ การจัดการเช่นนี้ทำให้ การทำงานค่อนข้างจะใช้เวลาคงที่ (O (1))

ดูเพิ่ม

• แถวคอย
• แถวคอยสองหน้า