موضوع مقاله: صف اولویت یکنواخت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # صف اولویت یکنواخت | مقدمه: در علوم رایانه صف اولویت یکنواخت یک نوع از نوع داده انتزاعی صف اولویت است که در آن اولویت‌های آیتم‌های استخراج شده باید یک دنباله یکنواخت را تشکیل دهند. | ## بخش 1: صف اولویت یکنواخت | به این معنا که، برای یک صف اولویت که در آن هر آیتم به ترتیب استخراج شده کمترین اولویت را دارد (min-heap)، حداقل اولویت باید به صورت یکنواخت افزایش یابد. فرض یکنواخت بودن به طور طبیعی در چندین کاربرد صف‌های اولویت پدیدار می‌شود و می‌توان به عنوان یک فرض ساده‌ساز برای سرعت بخشیدن به انواع خاصی از صف‌های اولویت استفاده شود. شرط لازم و کافی بر روی یک صف اولویت یکنواخت این است که هرگز تلاش نشود تا یک عنصر با اولویت پایین‌تر از آخرین عنصر استخراج شده اضافه شود. کاربرد ها صف‌های اولویت یکنواخت به طور طبیعی زمانی پدیدار می‌شوند که رویدادها بر اساس زمان مرتب شوند، مانند تایم‌اوت‌های شبکه ها یا شبیه‌سازی رویدادها به صورت گسسته. یک رویداد می‌تواند باعث شود که برخی از اقدامات برای زمانی در آینده برنامه‌ریزی شود، اما علیت (واقعی یا شبیه‌سازی شده) سبب میشود تلاش برای برنامه‌ریزی اقدامات در گذشته بی‌معنا شود. | ## بخش 2: صف اولویت یکنواخت | در الگوریتم دایکسترا برای مسئله کوتاه‌ترین مسیر، رئوس یک گراف وزن‌دار داده شده با ترتیب افزایش فاصله از راس شروع استخراج می‌شوند و از یک صف اولویت برای تعیین نزدیک‌ترین راس باقیمانده به راس شروع استفاده می‌شود. به طور مشابه، در الگوریتم‌های پاکسازی خطی در هندسه محاسباتی، رویدادهایی که در آن خط پاکساز یک نقطه مورد توجه را قطع می‌کند، با توجه به مختصات نقطه قطع شده، اولویت‌بندی می‌شود و این رویدادها به ترتیبی یکنواخت استخراج می‌شوند. یک ترتیب استخراج یکنواخت همچنین در نسخه بهترین-اول الگوریتم شاخه و حد نیز وجود دارد. ساختمان داده هر صف اولویت که بتواند عملیات استخراج غیر یکنواخت را انجام دهد، همچنین می‌تواند استخراج‌های یکنواخت را نیز انجام دهد، اما برخی از صف‌های اولویت مخصوص به این هستند که فقط برای استخراج‌های یکنواخت کار کنند یا زمانی که استخراج‌ها یکنواخت هستند بهتر عمل کنند. به عنوان مثال، صف سطلی یک ساختمان داده صف اولویت ساده است که شامل یک آرایه اندیس گذاری شده به وسیله ی اولویت است، که هر سلول آرایه حاوی یک سطل از آیتم‌ها با آن اولویت است. | ## بخش 3: صف اولویت یکنواخت | با این حال، هنگام استفاده به عنوان یک صف اولویت یکنواخت، جستجو برای سطل پر نشده بعدی بجای اینکه از شروع آرایه شروع شود، می‌تواند در اولویت عمل extract-min قبلی انجام شود. این بهینه‌سازی باعث می‌شود که زمان کل برای دنباله‌ای از عملیات‌ها متناسب با مجموع تعداد عملیات‌ها و طول آرایه باشد، بجای اینکه (مانند حالت غیر یکنواخت) حاصلضرب این دو مقدار.. چرکاسکی، گلدبرگ و سیلوراستاین (1999) یک طرح پیچیده‌تر به نام صف (HOT) Heap-on-top برای صف‌های اولویت یکنواخت با اولویت‌های از نوع عدد صحیح را توصیف می‌کنند، که بر اساس سطل‌بندی چند سطحی همراه با یک صف اولویت معمولی heap است. با استفاده از این روش، آن‌ها یک ساختار را به دست می‌آورند که می‌تواند آیتم‌ها را با اولویت‌های صحیح در محدوده 0 تا پارامتر C نگهداری کند. یک ساختار مرتبط دیگر از رامان (1996) به اولویت‌ها اجازه میدهد که اعداد صحیح ماشینی باشند، و همچنین اجازه عملیات وارد کردن و کاهش اولویت در زمان ثابت را می‌دهد، به همراه عملیات های extract-min ی که در یک صف اولویت با n آیتم‌ زمان متوسط .را می‌گیرد. | ## جمع‌بندی | این نتایج منجر به شتاب متناظر در الگوریتم دایکسترا برای گراف‌های با وزن یال های صحیح می‌شود.