مینیمم استک / مینیمم صف

از shaazzz
پرش به ناوبری پرش به جستجو

در این بخش می خواهیم راجع به حل این ۳ سوال صحبت کنیم : در ابتدا به ما یک سری می دهند که در آن ها از ما می خواهند کوچکترین عضو این ها رو با جواب بدیم . اول می خواهیم چگونگی حل این سوال ها را با استفاده از استک یاد بگیریم و سپس با استفاده از صف و در آخر می خواهیم از این دو داده ساختار برای پیدا کردن کوچکترین عدد در هر زیر آرایه ایی با طول و ، استفاده کنیم. توجه : در اینجا منظور از داده ساختار صف ، همان است .

بهینه سازی استک[ویرایش]

ما می خواهیم روش استفاده مان از استک را طوری بهبود ببخشیم که بتوانیم کوچکترین عضو در هر را با پیدا کنیم به طوری که این ویژگی استک که فقط می توان از یک طرف آن عضوی را اضافه کرد یا برداشت ، حفظ شود . ( می دانیم که استک شبیه کیسه ایی است که فقط از سر آن می توان استفاده کرد ) برای این کار باید اعضا استک را به صورت جفت یا همان ذخیره کنیم ، به طوری که ، خود عدد است و کوچکترین عضو استک با شروع از است .

stack<pair<int , int>> st;

این واضح است که برای پیدا کردن کوچکترین عضو فقط باید را چک کنیم .

پیاده سازی[ویرایش]

اضافه کردن عضو جدید:

int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});

حذف یک عضو:

int removed_element = st.top().first;
st.pop();

پیدا کردن کوچکترین عضو:

int minimum = st.top().second;

مثال : فرض کنید یکی از ها به این صورت است : . با توجه به کدی که داریم در ابتدا چون استک خالی است جفت را به استک اضافه می کنیم . بعد بین عضو جدید که همان است و که است ، مینیموم میگیریم . و جفت را به استک اضافه می کنیم . با توجه به این استدلال سپس جفت های به ترتیب از راست به چپ اضافه می شوند و مینیموم که همان است را به دست می آوریم .

بهینه سازی صف(روش ۱)[ویرایش]

حالا می خواهیم مساله بالا را با استفاده از حل کنیم . یک خوبی این روش این است که لازم به ذخیره تمام اعداد در صف نیست . ایده کلی این است که ما تنها اعدادی را در صف ذخیره می کنیم که برای مشخص کردن و پیدا کردن کوچکترین عضو لازم هستند( یعنی احتمال دارد که آنها کوچکترین باشند ) در واقع سعی داریم تا صف را طوری بسازیم که اگر از شروع کنیم ، اعضا به صورت صعودی باشند . در این صورت واضح است که کوچکترین عدد همیشه در سر صف قرار دارد . برای این کار لازم است قبل از اضاقه کردن یک عضو جدید ، تمام اعضای موجود در صف که از عضو جدید بزرگتر هستند را از صف پاک کنیم . به دو جیز باید توجه کرد : اول این که با انجام این کار همچنان حالت صعودی بودن حفظ می شود و دوم این که تمام اعدادی که قبل از اضافه کردن عضو جدید پاک کرده ایم ، نمی توانند کوچکترین باشند . وقتی می خواهیم عضوی را از سر صف حذف کنیم ، باید دقت کنیم . چون شاید عدد مورد نظر آنجا نباشد . زیرا وقتی می خواستیم یک عضو کوچکتر را به صف اضافه کنیم ، این عدد حذف شده باشد . بدین منظور ، لازم داریم تا مقدار عددی را که که حذف کردیم بدانیم . اگر عددی که در سر صف قرار دارد با مقدار عددی که می خواهیم حذف کنیم برابر بود ، آنگاه می توانیم آن عدد را از سر صف برداریم و اگر نه ، هیچ کاری نمی کنیم .

پیاده سازی[ویرایش]

deque<int> q;

پیدا کردن کوچکترین عضو:

int minimum = q.front();

اضافه کردن عضو جدید:

while (!q.empty() && q.back() > new_element)
    q.pop_back();
q.push_back(new_element);

حذف یک عضو:

if (!q.empty() && q.front() == remove_element)
    q.pop_front();

این واضح است که تمام این عملیات ها با انجام می شود . چون هر عدد تنها یک بار اضافه و حذف می شود .

بهینه سازی صف (روش ۲) :[ویرایش]

این روش درواقع نوع تغییر یافته ایی از روش ۱ است با این فرق که احتیاجی به دانستن عدد حذف شده نیست . برای انجام این کار اندیس هر عضو در صف را هم ذخیره کنیم و همچنین تعداد عضوهایی که اضافه یا حذف شده اند را نیز بدانیم .

پیاده سازی[ویرایش]

deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;

پیدا کردن کوچکترین عضو :

int minimum = q.front().first;

اضافه کردن عضو جدید:

while (!q.empty() && q.back().first > new_element)
    q.pop_back();
q.push_back({new_element, cnt_added});
cnt_added++;

حذف یک عضو:

if (!q.empty() && q.front().second == cnt_removed) 
    q.pop_front();
cnt_removed++;

بهینه سازی صف (روش ۳) :[ویرایش]

در این قسمت می خواهیم راه دیگری برای کوچکترین عضو با ارائه بدهیم . این راه ، پیاده سازی پیچیده تری نسبت به روش های قبلی دارد و تمام اعضا در صف ذخیره نمی شوند . همچنین برای برداشتن یک عضو از سر صف لازم به دانستن مقدار آن نیست . درواقع ایده کلی این است که می خواهیم این روش را تبدیل به روشی کنیم که با استک این مسائله را حل کردیم . فقط کافی است که یادبگیریم چگونه صف را با دو استک شبیه سازی کنیم . ابتدا دوتا استک با نام های می سازیم . اعضا جدید را در می ریزیم و عمل حذف کردن یک عضو را فقط روی انجام می دهیم . اگر خالی بود و نمی توانستیم این عمل را انجام بدهیم ، تمام اعضای موجود در را به انتقال می دهیم . (واضح است که بعد از این کار ترتیب قرار گرفتن اعضا در برعکس ترتیبی است که در داشته اند.) و درآخر کوچکترین عضو در صف ، مینیموم مقدار کوجکترین عضو در هر استک است . بنابراین اجرای این عملیات ها با قابل انجام است . زیرا هر عضو تنها ۱بار به اضافه می شود ، ۱بار از به منتقل می شود و ۱بار از حذف می شود .

پیاده سازی[ویرایش]

stack<pair<int, int>> s1, s2;

پیدا کردن کوچکترین عضو :

if (s1.empty() || s2.empty()) 
    minimum = s1.empty() ? s2.top().second : s1.top().second;
else
    minimum = min(s1.top().second, s2.top().second());

اضافه کردن عضو جدید (adding an element) :

int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});


حذف یک عضو (removing an element) :

if (s2.empty()) {
    while (!s1.empty()) {
        int element = s1.top.first();
        s1.pop();
        int minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
    }
}
int remove_element = s2.top().first;
s2.pop();

پیدا کردن کوچکترین عضو برای تمام زیرآرایه ها با طول ثابت[ویرایش]

فرض کنید آرایه ایی به نام با طول داریم . می خواهیم کوچکترین عضو در هر زیرآرایه با طول که را پیدا کنیم . درواقع باید پیدا کنیم : و ما باید این مسئله را با حل کنیم . ما می توانیم از هر سه روشی که برای تعدیل صف ارائه شد ، استفاده کنیم . اگر بخواهیم به طور خلاصه راه را بگوییم ، داریم : ابتدا عضو اول آرایه را در صف می ریزیم ، سپس کوچکترین آنها را پیدا کرده و خروجی می دهیم . بعد اولین عضو آرایه را پیدا کرده ، آن را حذف می کنیم و عضو ام را به صف اضافه می کنیم ، سپس دوباره مینیموم را پیدا کرده و خروجی می دهیم و ....