صف اولویت یکنواخت

در علوم رایانه صف اولویت یکنواخت یک نوع از نوع داده انتزاعی صف اولویت است که در آن اولویت‌های آیتم‌های استخراج شده باید یک دنباله یکنواخت را تشکیل دهند. به این معنا که، برای یک صف اولویت که در آن هر آیتم به ترتیب استخراج شده کمترین اولویت را دارد (min-heap)، حداقل اولویت باید به صورت یکنواخت افزایش یابد. برعکس، برای یک max-heap حداکثر اولویت باید به صورت یکنواخت کاهش یابد. فرض یکنواخت بودن به طور طبیعی در چندین کاربرد صف‌های اولویت پدیدار می‌شود و می‌توان به عنوان یک فرض ساده‌ساز برای سرعت بخشیدن به انواع خاصی از صف‌های اولویت استفاده شود. شرط لازم و کافی بر روی یک صف اولویت یکنواخت این است که هرگز تلاش نشود تا یک عنصر با اولویت پایین‌تر از آخرین عنصر استخراج شده اضافه شود.^[۱]^: 128

کاربرد ها

صف‌های اولویت یکنواخت به طور طبیعی زمانی پدیدار می‌شوند که رویدادها بر اساس زمان مرتب شوند، مانند تایم‌اوت‌های شبکه ها یا شبیه‌سازی رویدادها به صورت گسسته. یک رویداد می‌تواند باعث شود که برخی از اقدامات برای زمانی در آینده برنامه‌ریزی شود، اما علیت (واقعی یا شبیه‌سازی شده) سبب میشود تلاش برای برنامه‌ریزی اقدامات در گذشته بی‌معنا شود. در الگوریتم دایکسترا برای مسئله کوتاه‌ترین مسیر، رئوس یک گراف وزن‌دار داده شده با ترتیب افزایش فاصله از راس شروع استخراج می‌شوند و از یک صف اولویت برای تعیین نزدیک‌ترین راس باقیمانده به راس شروع استفاده می‌شود. بنابراین، در این برنامه، عملیات های صف اولویت از نوع یکنواخت هستند.^[۱]^:128 به طور مشابه، در الگوریتم‌های پاکسازی خطی در هندسه محاسباتی، رویدادهایی که در آن خط پاکساز یک نقطه مورد توجه را قطع می‌کند، با توجه به مختصات نقطه قطع شده، اولویت‌بندی می‌شود و این رویدادها به ترتیبی یکنواخت استخراج می‌شوند. یک ترتیب استخراج یکنواخت همچنین در نسخه بهترین-اول الگوریتم شاخه و حد نیز وجود دارد.

ساختمان داده

هر صف اولویت که بتواند عملیات استخراج غیر یکنواخت را انجام دهد، همچنین می‌تواند استخراج‌های یکنواخت را نیز انجام دهد، اما برخی از صف‌های اولویت مخصوص به این هستند که فقط برای استخراج‌های یکنواخت کار کنند یا زمانی که استخراج‌ها یکنواخت هستند بهتر عمل کنند. به عنوان مثال، صف سطلی یک ساختمان داده صف اولویت ساده است که شامل یک آرایه اندیس گذاری شده به وسیله ی اولویت است، که هر سلول آرایه حاوی یک سطل از آیتم‌ها با آن اولویت است. عملیات extract-min یک جستجوی ترتیبی برای اولین سطل پر نشده را انجام می‌دهد و یک آیتم دلخواه در آن سطل را انتخاب می‌کند. برای استخراج‌های غیر یکنواخت، یک عمل extract-min در (بدترین حالت) زمان متناسب با طول آرایه (تعداد اولویت‌های مختلف) می‌برد. با این حال، هنگام استفاده به عنوان یک صف اولویت یکنواخت، جستجو برای سطل پر نشده بعدی بجای اینکه از شروع آرایه شروع شود، می‌تواند در اولویت عمل extract-min قبلی انجام شود. این بهینه‌سازی باعث می‌شود که زمان کل برای دنباله‌ای از عملیات‌ها متناسب با مجموع تعداد عملیات‌ها و طول آرایه باشد، بجای اینکه (مانند حالت غیر یکنواخت) حاصلضرب این دو مقدار.^[۲]

چرکاسکی، گلدبرگ و سیلوراستاین (1999) یک طرح پیچیده‌تر به نام صف (HOT) Heap-on-top برای صف‌های اولویت یکنواخت با اولویت‌های از نوع عدد صحیح را توصیف می‌کنند، که بر اساس سطل‌بندی چند سطحی همراه با یک صف اولویت معمولی heap است. با استفاده از این روش، آن‌ها یک ساختار را به دست می‌آورند که می‌تواند آیتم‌ها را با اولویت‌های صحیح در محدوده 0 تا پارامتر C نگهداری کند. صف HOT برای هر عمل وارد کردن یا کاهش اولویت، زمان ثابت و برای عمل extract-min زمان متوسط $O((\log C)^{1/3}(\log \log C)^{1/2})$ را استفاده می‌کند.^[۳] یک ساختار مرتبط دیگر از رامان (1996) به اولویت‌ها اجازه میدهد که اعداد صحیح ماشینی باشند، و همچنین اجازه عملیات وارد کردن و کاهش اولویت در زمان ثابت را می‌دهد، به همراه عملیات های extract-min ی که در یک صف اولویت با n آیتم‌ زمان متوسط $O({\sqrt {\log n\log \log n}})$ ^[۴]را می‌گیرد. این نتایج منجر به شتاب متناظر در الگوریتم دایکسترا برای گراف‌های با وزن یال های صحیح می‌شود.

References

↑ ^۱٫۰ ^۱٫۱ Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.
↑ Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN 978-0-387-94860-7.
↑ Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (August 1999), Buckets, heaps, lists, and monotone priority queues, vol. 28, pp. 1326–1346 (electronic), CiteSeerX 10.1.1.49.8244, doi:10.1137/S0097539796313490.
↑ Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, vol. 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, S2CID 17004419.

[mehlhorn-1] ۱٫۰ ^۱٫۱ Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.

[2] Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN 978-0-387-94860-7.

[3] Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (August 1999), Buckets, heaps, lists, and monotone priority queues, vol. 28, pp. 1326–1346 (electronic), CiteSeerX 10.1.1.49.8244, doi:10.1137/S0097539796313490.

[4] Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, vol. 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, S2CID 17004419.

[۱]

[۲]

[۳]

[۴]