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

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

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

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

จุดเด่น

แก้

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

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

แก้
  • เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (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))

ดูเพิ่ม

แก้