STL priority_queue

เป็น data structure แบบเรียงลำดับข้อมูลตลอดเวลา ดูรายละเอียดที่ priority queue , heap

การใช้งาน

ต้องเรียกใช้ header file "queue" และเรียกใช้ namespace std

#include <queue>
 
using namespace std;

การประกาศตัวแปร

ให้ T คือ datatype ใดๆ และ var คือชื่อตัวแปร มีรูปแบบการประกาศตัวแปร priority_queue ดังนี้

priority_queue <T> var;

หรือหากต้องการเขียน compare class เองก็จะใช้รูปแบบ

priority_queue <T,vector<T>,cmpclass> var;

รายละเอียด compare class อ่านที่นี่

method

push

คำอธิบาย เป็นการเพิ่มข้อมูลชนิด T ลง priority_queue เหมือนการ insert ใช้เวลา O$(log(n))$
parameter มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง priority_queue
return ไม่มี
prototype void push(T);

pop

คำอธิบาย เป็นการลบข้อมูลชนิด T ทางด้านปลายของ priority_queue เหมือนการ extract ใช้เวลา $O(log(n))$
ข้อควรระวัง : หาก size ของ priority_queue เป็น 0 จะเกิด error
parameter ไม่มี
return ไม่มี
prototype void pop();

top

คำอธิบาย เป็นการหาค่าที่อยู่ด้านปลายของ priority_queue ใช้เวลา $O(1)$
ข้อควรระวัง : หาก size ของ priority_queue เป็น 0 จะเกิด error
parameter ไม่มี
return ข้อมูลชนิด T ที่อยู่ด้านปลายของ priority_queue
prototype T top();

size

คำอธิบาย เป็นการหาว่าขณะนี้ priority_queue มีขนาดเท่าไหร่ ใช้เวลา $O(1)$
parameter ไม่มี
return จำนวนเต็ม บอกถึงขนาดของ priority_queue
prototype int size();

empty

คำอธิบาย เป็นการหาว่าขณะนี้ priority_queue ว่างหรือไม่ ใช้เวลา $O(1)$
parameter ไม่มี
return ค่า true เมื่อ priority_queue ว่าง (ขนาดเป็น 0)
ค่า false เมื่อ priority_queue ไม่ว่าง (ขนาดมากกว่า 0)
prototype bool empty();

รายละเอียดเพิ่มเติม

เนื่องจาก priority_queue จะทำการเรียงข้อมูลตลอดเวลา ดังนั้นจึงต้องมีเกณฑ์ในการเรียงหรือการเปรียบเทียบเกิดขึ้น เพราะ priority_queue ไม่อาจรู้ได้ว่าค่าไหนควรมาก่อนค่าไหน หากไม่มีการเปรียบเทียบเกิดขึ้น

สามารถแบ่งการประกาศ priority_queue ได้เป็น 2 รูปแบบ

  • ระบุ compare class จะเหมือนตัวอย่างที่ 2 ในหัวข้อการประกาศตัวแปร ในกรณีนี้ priority_queue จะดูว่าเกณฑ์การเปรียบเทียบค่าเป็นอย่างไรตาม compare class
  • ไม่ระบุ compare class จะเหมือนตัวอย่างที่ 1 ในหัวข้อการประกาศตัวแปร ในกรณีนี้ priority_queue จะใช้ less เป็น compare class โดยอัตโนมัติ
    • หาก datatype ที่ระบุเป็น primitive datatype จะเป็นการเรียงแบบน้อยไปมาก
    • หาก datatype ที่ระบุเป็น STL string (std::string) จะเป็นการเรียงแบบ lexicographic order
    • หาก datatype ที่ระบุเป็น struct ที่มีการ overloading operator < จะเกิดการเรียงตามที่กำหนดใน overloading operator <
    • หาก datatype ที่ระบุเป็น datatype อื่นๆซึ่ง less ไม่รู้จัก จะเกิด compilation error ขึ้น

หากการเรียงของ priority_queue เป็นการเรียงแบบน้อยไปมาก ข้อมูลด้านหน้าของ priority_queue จะมีค่าน้อยสุดไปเรื่อยๆ
จนถึงข้อมูลด้านปลายมีค่ามากสุด แต่ในการใช้ top หรือ pop จะเป็นการดำเนินการกับข้อมูลด้านปลาย
เมื่อมีการเรียก top หรือ pop จึงเป็นการดำเนินการกับค่ามากที่สุด ฉะนั้นหากต้องการให้ top , pop ดำเนินการกับค่าอื่นๆแทน
ก็ต้องเปลี่ยนวิธีการเปรียบเทียบใหม่ (เช่นต้องการให้ top , pop ดำเนินการกับค่าน้อยสุด ก็ต้องเรียงจากมากไปน้อยแทน)

การใช้ compare class

compare class คือ class/struct ที่สร้างขึ้นมาเพื่อบอกให้ priority_queue รู้ว่า ข้อมูลไหนควรมาก่อน ข้อมูลไหนควรมาหลัง (จะเรียงข้อมูลอย่างไรดี) โดยทั่วไปหากไม่กำหนด compare class ให้ priority_queue จะใช้ less เป็น compare class อัตโนมัติ (นั่นคือเรียงแบบน้อยไปมาก)

หลักการเขียน compare class

  • หากต้องการให้ a มาก่อน b ให้ return true
  • หากต้องการให้ b มาก่อน a ให้ return false

กรณี a สำคัญเท่า b จะ return true หรือ false ก็ได้ เพราะถ้า a กับ b สำคัญพอๆกัน อะไรจะมาก่อนมันก็ไม่สำคัญ !

ตัวอย่าง compare class โดยเรียง int

struct cmpclass{
    bool operator()(int a, int b){
        return a < b;
    }
};

จากตัวอย่าง เราสร้าง struct/class ชื่อ cmpclass ภายในมีการ overloading operator () โดยรับค่า a และ b มา
กรณี a < b เราจะ return ค่า true ซึ่งก็คือการเรียงลำดับจากน้อยไปมากนั่นเอง
และในกรณีนี้ หากมีการเรียกใช้ pop , top ก็จะเป็นการดำเนินการกับค่าใน priority_queue ซึ่งมากที่สุด (เหมือนใช้ less)

หากต้องการให้ pop , top ดำเนินการกับค่าน้อยสุดก็คือต้องเปลี่ยนการเรียงเป็นมากไปน้อยแทน สามารถเขียนโค้ดได้ตามนี้

struct cmpclass{
    bool operator()(int a, int b){
        return a > b;
    }
};

ตัวอย่าง cmpclass โดยเรียง struct ตามค่า p จากน้อยไปมาก

struct T{
    int p,q;
};
 
struct cmpclass{
    bool operator()(T a, T b){
        return a.p < b.p;
    }
};

การ pass by reference

มีปัญหาอีกอย่างหนึ่งคือ ในกรณีที่ struct มีขนาดใหญ่มาก การส่งผ่าน struct แบบ pass by value บ่อยๆจะเสียเวลามาก
ดังนั้น สามารถแก้ไขปัญหาโดย pass by reference แทน หากนำโค้ดจากตัวอย่างที่แล้วมาแก้เพิ่มจะได้ดังนี้

struct T{
    int p,q;
};
 
struct cmpclass{
    bool operator()(const T& a, const T& b){
        return a.p < b.p;
    }
};

กล่าวคือ เราจะเปลี่ยน "T val" ไปเป็น "const T& val" แทน

การ Overloading Operator < ของ struct

วิธีนี้ใช้ได้กับ datatype ที่เป็น struct เท่านั้น

แนวคิดวิธีนี้คือ เราสามารถกำหนดความหมายของ $<$ ขึ้นมาเองให้กับ struct ใดๆได้ เช่น
ให้ struct มีจำนวนเต็ม aa กับ bb เป็นสมาชิก
เราสามารถกำหนดความหมายของ $<$ ขึ้นมาเองให้ $a < b$ return ค่า true เมื่อ a.aa $>$ b.aa
เพราะฉะนั้นหาก a.aa = 3 และ b.aa = 5
จะได้ว่า $b < a$ return ค่า true (เพราะ b.aa $>$ a.aa)
แต่ $a < b$ return ค่า false (เพราะ b.aa $\not\gt$ a.aa)

การเขียนโค้ด เราจะ overloading operator < โดยรับ T เข้ามา (จากตัวอย่างที่แล้ว เรารู้ว่าควรใช้ pass by reference เพื่อไม่ให้เกิดปัญหา)
จากนั้น เราจะเขียนเปรียบเทียบค่าของ T ที่เพิ่งรับเข้ามากับสมาชิกปัจจุบัน

struct T{
    int aa,bb;
    bool operator<(const T &p)const{
        return aa > p.aa;
    }
};

จากโค้ดตัวอย่างเป็นการบอกว่า หาก aa ของตัวปัจจุบัน มีค่ามากกว่า aa ของ struct อีกตัวที่รับเข้ามา จะ return true

เพราะฉะนั้น เมื่อเรากำหนด $<$ ให้ struct เรียบร้อยแล้ว เราก็ไม่จำเป็นจะต้องใช้ cmpclass อีก !

code STL priority_queue

#include <cstdio>
#include <queue>
 
using namespace std;
 
struct ST{
    int a,b;
    bool operator<(const ST &aa)const{
        return a < aa.a;
    }
};
 
int main(){
    priority_queue <int> Q; // []
    Q.push(13); // [13]
    Q.push(12); // [12,13]
    Q.push(11); // [11,12,13]
    Q.push(10); // [10,11,12,13]
    printf("%d\n", Q.top()); // => 13
    Q.pop(); // [10,11,12]
    printf("%d\n", Q.size()); // => 3
    while(!S.empty())Q.pop(); // []
    Q.pop() // => Error
    Q.top() // => Error
 
    ST tmp;
    priority_queue <ST> T; // []
    tmp.a = 5;
    tmp.b = 3;
    T.push(tmp); // [(5,3)]
    tmp.a = 4;
    tmp.b = 10;
    T.push(tmp); // [(4,10),(5,3)]
    printf("%d\n", T.top().b); // => 3
    return 0;
}
stl
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License