صف اولویت‌دار دوطرفه
در علوم رایانه، صف اولویت دار دوطرفه یا هرم دوطرفه (به انگلیسی: DEPQ) داده ساختاری شبیه هرم یا صف دوطرفه می‌باشد که برای حذف عضو کمینه و بیشینه بهینه است. هر عضو در صف اولویت دار دوطرفه دارای یک اولویت یا ارزش می‌باشد و می‌توان عناصر را به ترتیب صعودی یا نزولی با پیچیدگی زمانی برابر، حذف کرد.[۱][۲][۳]
عملیات‌ها
[ویرایش]()isEmpty
چک می‌کند صف خالی است یا نه و اگر خالی بود مقدار درست (به انگلیسی: true) برمی‌گرداند.
()size
تعداد کل عناصر موجود در صف را برمی‌گرداند.
()getMin
عنصر با اولویت کمینه را برمی‌گرداند.
()getMax
عنصر با اولویت بیشینه را برمی‌گرداند.
x)put)
عنصر x را به صف اضافه می‌کند.
()removeMin
عنصر با اولویت کمینه را حذف می‌کند و آن را بازمی‌گرداند.
()removeMax
عنصر با اولویت بیشینه را حذف می‌کند و آن را بازمی‌گرداند. اگر عملیاتی بر دو عنصر با اولویت یکسان اجرا شود، اولویت با عنصری است که ابتدا وارد شده‌است.
پیاده‌سازی
[ویرایش]صف اولویت دار دوطرفه می‌تواند با درخت دودویی جستجو متعادل (به انگلیسی: balanced binary search trees) یا داده ساختاری خاص مثل min-max heap و pairing heap پیاده‌سازی شود.
روش ساختار دوتایی
[ویرایش]دراین روش دو داده ساختار هرم کمینه و هرم بیشینه با عناصر یکسان داریم که هر دوعنصر یکسان در دو هرم به هم اشاره (به انگلیسی: pointer) می‌کنند.
تناظر کلی (به انگلیسی: Total correspondence)
[ویرایش]در این روش، اگر عناصر را مرتب کنیم یکی در میان هنصرها در هرم بیشینه و کمینه نگه می‌داریم یعنی نصف عناصر در هرم کمینه و نصف دیگر هرم بیشینه قرار می‌گیرد و هر عنصر به عنصر بعدی خود - که بدیهی است در هرم دیگر قرار دارد – اشاره می‌کند.
هرم ورودی (به انگلیسی: Interval heaps)
[ویرایش]دراین روش داده ساختار یک هرم است که هر گره در آن دوعضو دارد و براساس عضو اول هرم کمینه و براساس عضو دوم هرم بیشینه می‌باشد.
پیچیدگی زمانی
[ویرایش]وقتی صف اولویت دار دوطرفه با هرم فاصله پیاده‌سازی شود و n عنصر داشته باشد پیچیدگی زمانی هر عملیات به شرح زیر است.
| عملیات | پیچیدگی زمانی |
|---|---|
| init() | O(n) |
| isEmpty() | O(1) |
| getmin() | O(1) |
| getmax() | O(1) |
| size() | O(1) |
| insert(x) | O(log n) |
| removeMin() | O(log n) |
| removeMax() | O(log n) |
وقتی صف اولویت دار دوطرفه با هرم یا هرم جفت پیاده‌سازی شود پیچیدگی زمانی عملیات‌های مختلف به شرح زیر است. پیچیدگی زمانی برای هرم جفت به صورت سرشکن است.
| عملیات | پیچیدگی زمانی |
|---|---|
| isEmpty() | O(1) |
| getmin() | O(1) |
| getmax() | O(1) |
| insert(x) | O(log n) |
| removeMax() | O(log n) |
| removeMin() | O(log n) |
کاربرد
[ویرایش]یکی از کاربردهای مهم مرتب‌سازی خارجی است. ابتدا نیمه از داده‌ها را در صف اولویت دار دوطرفه می‌ریزیم حال باقی عناصر را یکی یکی می‌خوانیم و اگر آن عنصر کوچکتر مساوی عنصر کمینه در صف اولویت دار دوطرفه بود، آن را جزو عنصر دسته چپ و اگر بزرگتر مساوی عنصر بیشینه در صف اولویت دار دوطرفه بود، آن را در دسته راست قرار می‌دهیم در غیر این صورت عنصر کمینه یا بیشینه را حذف می‌کنیم. اگر عنصر کمینه را حذف کردیم عنصر جدید را به دسته راست و اگر عنصر کمینه را حذف کردیم عنصر جدید را به دسته چپ اضافه می‌کنیم. عناصر وجود در صف اولویت دار دوطرفه همان عناصر میانی مرتب شده هستند وعناصر چپ و راست را مرتب می‌کنیم.[۴]
منابع
[ویرایش]- ↑ Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 211. ISBN 9780521880374.
- ↑ Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues, Sartaj Sahni, 1999.
- ↑ "Depq - Double-Ended Priority Queue". Archived from the original on 2012-04-25. Retrieved 2011-10-04.
- ↑ «Higher Education Support | McGraw Hill Higher Education». www.mheducation.com (به انگلیسی). دریافت‌شده در ۲۰۲۴-۱۰-۲۸.