پرش به محتویات

پشته کمینه / صف کمینه

در این مقاله به سه مسئله می‌پردازیم: ابتدا یک پشته را طوری تغییر می‌دهیم که بتوانیم کوچکترین عنصر آن را در زمان $O(1)$ پیدا کنیم، سپس همین کار را با یک صف انجام می‌دهیم، و در نهایت از این داده‌ساختارها استفاده می‌کنیم تا کمینه را در تمام زیرآرایه‌های یک آرایه با طول ثابت، در زمان $O(n)$ پیدا کنیم.

پیاده‌سازی پشته

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

برای این کار، ما عناصر را به صورت زوج در پشته ذخیره می‌کنیم: خود عنصر و کمینه تمام عناصر پشته تا آن لحظه.

stack<pair<int, int>> st;

واضح است که برای پیدا کردن کمینه در کل پشته، کافی است فقط به مقدار stack.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;

پیاده‌سازی صف (روش اول)

حالا می‌خواهیم همین عملیات‌ها را با یک صف انجام دهیم، یعنی می‌خواهیم عناصر را به انتها اضافه کرده و از ابتدا حذف کنیم.

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

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

پیاده‌سازی عملیات‌های بالا را در نظر بگیرید:

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)$ می‌برند (چون هر عنصر فقط یک بار می‌تواند به صف اضافه و از آن خارج شود).

پیاده‌سازی صف (روش دوم)

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

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) را بررسی می‌کنیم تا بتوانیم کمینه را در زمان O(1) پیدا کنیم. پیاده‌سازی این روش کمی پیچیده‌تر است، اما این بار تمام عناصر را واقعاً ذخیره می‌کنیم. و همچنین می‌توانیم یک عنصر را از ابتدای صف بدون دانستن مقدارش حذف کنیم.

ایده این است که مسئله را به مسئله‌ی پشته‌ها (stacks) کاهش دهیم، که قبلاً توسط ما حل شده است. بنابراین، فقط باید یاد بگیریم که چگونه با استفاده از دو پشته، یک صف را شبیه‌سازی کنیم.

دو پشته به نام‌های s1 و s2 می‌سازیم. البته این پشته‌ها از نوع اصلاح‌شده خواهند بود، تا بتوانیم کمینه را در زمان O(1) پیدا کنیم. عناصر جدید را به پشته‌ی s1 اضافه می‌کنیم و عناصر را از پشته‌ی s2 حذف می‌کنیم. اگر در هر زمانی پشته‌ی s2 خالی شد، تمام عناصر را از s1 به s2 منتقل می‌کنیم (این کار اساساً ترتیب آن عناصر را معکوس می‌کند). در نهایت، پیدا کردن کمینه در یک صف، شامل پیدا کردن کمینه‌ی هر دو پشته است.

بنابراین، همه‌ی عملیات را به طور متوسط در زمان O(1) انجام می‌دهیم (هر عنصر یک بار به پشته‌ی s1 اضافه می‌شود، یک بار به s2 منتقل می‌شود و یک بار از s2 بیرون کشیده می‌شود).

پیاده‌سازی:

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

  • پیدا کردن کمینه: 

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

  • اضافه کردن عنصر: 

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

  • حذف کردن یک عنصر: 

    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 \le N$ به ما داده شده است. ما باید کمینه‌ی هر زیرآرایه به طول $M$ در این آرایه را پیدا کنیم، یعنی باید مقادیر زیر را بیابیم:

$$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],~\dots~, \min_{N-M \le i \le N-1} A[i]$$

باید این مسئله را در زمان خطی، یعنی $O(n)$، حل کنیم.

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

سوالات