خانه ویکی

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

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

بهینه سازی استک

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

stack<pair<int , int>> st;

این واضح است که برای پیدا کردن کوچکترین عضو فقط باید $set.top().second$ را چک کنیم .

پیاده سازی

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

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;

مثال : فرض کنید یکی از $query$ها به این صورت است : ${13 , 5 , 9 , 8}$ . با توجه به کدی که داریم در ابتدا چون استک خالی است جفت $(8 , 8)$ را به استک اضافه می کنیم . بعد بین عضو جدید که همان $9$ است و $set.top().second$ که $8$ است ، مینیموم میگیریم . و جفت $(9 , 8)$ را به استک اضافه می کنیم . با توجه به این استدلال سپس جفت های $(5 , 5) , (5 , 13)$ به ترتیب از راست به چپ اضافه می شوند و مینیموم که همان $set.top().second = 5$ است را به دست می آوریم .

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

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

پیاده سازی

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();

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

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

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

پیاده سازی

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++;

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

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

پیاده سازی

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();

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

فرض کنید آرایه ایی به نام $A$ با طول $n$ داریم . می خواهیم کوچکترین عضو در هر زیرآرایه با طول $m$ که $m <= n$ را پیدا کنیم . درواقع باید پیدا کنیم : $min A[i] | 0 <= i <= m - 1 , min A[i] | 1 <= i <= M , …. , min A[i] | n - m <= i <= n - 1$ و ما باید این مسئله را با $O(n)$ حل کنیم . ما می توانیم از هر سه روشی که برای تعدیل صف ارائه شد ، استفاده کنیم . اگر بخواهیم به طور خلاصه راه را بگوییم ، داریم : ابتدا $m$ عضو اول آرایه را در صف می ریزیم ، سپس کوچکترین آنها را پیدا کرده و خروجی می دهیم . بعد اولین عضو آرایه را پیدا کرده ، آن را حذف می کنیم و عضو $m$ام را به صف اضافه می کنیم ، سپس دوباره مینیموم را پیدا کرده و خروجی می دهیم و ….