حل تشریحی سوال شماره 65 طراحی الگوریتم

فرض کنید یک ساختار داده جدید به نام لیست اولویت دار پویا (Dynamic Priority List) دارید. این ساختار داده از لیستی از گره ها تشکیل شده است که هر گره دارای یک مقدار کلید و یک اولویت است. عمل های زیر، بر روی این ساختار داده تعریف شده اند:

• $insert(x,p)$: افزودن یک عنصر با کلید x و الویت p به لیست
• $DeleteMax\left(\right)$: حذف گره ای که دارای بیشترین اولویت است. اگر چند گره دارای اولویت یکسان باشند. اولین گره از سمت چپ حذف می شود.
• $FindMedian()$: یافتن مقدار میانه از بین تمامی کلیدهای موجود در لیست
• $IncreasePriority(x,k)$: افزایش اولویت عنصر با کلید x به اندازه k

هر کدام از این عملیات باید در کمترین پیچیدگی زمانی ممکن انجام شوند. حال، کدام یک از روش های زیر مناسب ترین ساختار داده ترکیبی برای پیاده سازی لیست اولویت دار پویا است، به گونه ای که همه عملیات با پیچیدگی بهینه انجام شوند؟