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

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

توی این مقاله می‌خوایم سه تا مسئله رو با هم ببینیم:

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

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

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

یادته که؟ توی پشته، ما فقط از یه طرف آیتم‌ها رو اضافه و حذف می‌کنیم. (زمان همه‌ی کارها توی پشته $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++;

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

اینجا یه روش دیگه برای دستکاری صف رو می‌بینیم که بشه باهاش کمینه رو توی زمان 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)$.

سوالات