صف ساختاری هست که ما فقط به عنصر اول دسترسی داریم . (یعنی به همون ترتیبی که عناصر اضافه میشن بهشون دسترسی هم داریم)
صف اولویت صفی هست که اولین عنصری که بهش دسترسی داریم همیشه بزرگترین یا کوچکترین عنصر ما هست .
که بر همین اساس به 2 دسته max priority queue و min priority queue تقسیم میشه.
priority queue بوسیله ساختار max heap پیاده سازی میشه که این جا توضیح داده شده .
داخل ++C این ساختار با اسم std::priority_queue وجود داره و ساختار درونی رو میشه تعیین کرد یعنی میشه تغیین کرد عناصر داخل وکتور ذخیره بشن یا list ,...
priority queue سه تا عملیات اصلی داره push و pop , top .
-
push عنصر اضافه می کنه به صف .
-
top عنصر اول رو بهمون میده
-
pop عنصر اول رو حذف می کنه
چون این ساختار از heap استفاده می کنه برای push_back یکبار push_back هیپ رو انجام میده که از (logn) هست یک بار هم push_back ساختار داخلی مثلا اگر vector باشه یکبار هم push_back وکتور انجام میشه که constant amortized ,و از (1)O هست .
عملیات top از (1)O هست .
عملیات pop هم یکبار pop ساختار هیپ رو صدا میزنه که از (O(logn هست یکبار هم pop برای ساختار داخلی .
مثال از استفاده داخل ++C :
#include <iostream>
#include <queue>
#include <vector>
int main ()
{
std::priority_queue<int, std::vector<int>> queue;
queue.push(6); queue.push(3); queue.push(7);
queue.push(9); queue.push(2); queue.push(5);
std::cout<<queue.top()<<'\n';//bozorgtaring onsor yani 9 chap mishe
queue.pop();//hazf onsor aval
std::cout<<queue.top();//bozorgtaring onsor badi yani 7 chap mishe
return 0;
}