سوال ۶۵ کنکور ارشد علوم کامپیوتر ۱۴۰۴

فرض کنید می‌خواهیم یک داده‌ساختار طراحی کنیم که هم‌زمان قابلیت‌های یک صف معمولی و یک صف اولویت (Priority Queue) را داشته باشد. این داده‌ساختار باید بتواند عملیات‌های زیر را انجام دهد:

• افزودن یک عنصر $\text{Enqueue}(x,p)$: عنصر x با اولویت p به داده‌ساختار اضافه می‌شود.
• $\text{Dequeue Max}$: عنصر با بیشترین اولویت از داده‌ساختار حذف و بازگردانده می‌شود.
• $\text{Dequeue First}$: اولین عنصری که به داده‌ساختار اضافه شده، حذف و بازگردانده می‌شود.

اگر این داده‌ساختار را با استفاده از پشته (Stacks) پیاده‌سازی کنیم، حداقل پیچیدگی زمانی سرشکن عملیات‌های $\text{Dequeue Max \& Dequeue First}$ برای n عملیات چقدر می‌تواند باشد؟