حل تشریحی سوال شماره 4 حل مسئله
کنکور دکتری مهندسی فناوری اطلاعات (IT) 1404
فرض کنید یک سیستم مدیریت جریان داده ها (Data Stream Management System) دارید که جریان مداومی از اعداد صحیح را در قالب یک دنباله ورودی پیوسته دریافت میکند. هدف شما این است که ساختاری پیاده سازی کنید که از طریق آن بتوانید عملیات زیر را به طور کارآمد انجام دهید:
Insert(x) :اضافه کردن عدد x به جریان
FindMedian :پیدا کردن میانه اعداد موجود در هر لحظه از جریان
GetTopK(k) :بازگرداندن k عدد شامل بزرگ ترین عددهای موجود در جریان
Delete(x) :حذف عدد مشخص x از جریان در صورتی که وجود داشته باشد
با توجه به اینکه داده ها به صورت پیوسته و بدون توقف وارد میشوند نیاز است که تمام عملیات بالا در پیچیدگی زمانی زیر خطی (Sub-linear) یا نزدیک به خطی انجام شوند. کدام یک از ساختارهای داده زیر مناسب ترین انتخاب برای پیاده سازی این سیستم است به گونه ای که تمامی عملیات با کمترین پیچیدگی ممکن انجام شوند؟
استفاده از یک درخت جستجوی دو دویی متوازن (Balanced Binary Search Tree) برای نگهداری تمامی اعداد در جریان به طوری که میانه و بزرگترین مقادیر به صورت مرتب مستقیماً نگهداری شوند.
ترکیب یک هرم بیشینه (Max-Heap) برای مدیریت بزرگترین اعداد و یک هرم کمینه Min-eap برای مدیریت کوچک ترین اعداد به همراه یک جدول هش Hash Table برای دسترسی سریع به اعداد
استفاده از یک درخت فیبوناچی (Fibonacci Heap) برای مدیریت میانه و بزرگترین مقادیر به همراه یک جدول هش برای دسترسی سریع به به اعداد در جریان
استفاده از یک لیست پیوندی دو طرفه به همراه یک آرایه مرتب برای نگهداری و دسترسی سریع به میانه و بزرگترین مقادیر