یادداشت کامل الگوریتم

هیپ

Heap

Heap یک درخت کامل است که معمولاً داخل Array ذخیره می‌شود. در Min-Heap کوچک‌ترین مقدار در ریشه و در Max-Heap بزرگ‌ترین مقدار در ریشه قرار می‌گیرد.

نوعساختمان دادهدستهساختمان دادهسطحپایهپیچیدگی معمولpeek O(1), insert/remove O(log n)

جواب کوتاه و حرفه‌ای

اول این مفهوم را در ذهن نگه دار

توضیح ساده

چطور کار می‌کند؟ ساده و مرحله‌ای

Heap کاملاً مرتب نیست؛ فقط رابطه parent/child را تضمین می‌کند.

بعد از insert یا حذف ریشه، با حرکت دادن مقدار به بالا یا پایین property هیپ دوباره برقرار می‌شود.

روند اجرا

الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان

مقدار جدید را انتهای Array قرار بده.

تا وقتی property نقض شده آن را بالا ببر.

برای حذف root آخرین مقدار را به ریشه بیاور و آن را به پایین heapify کن.

یک مثال کوچک برای فهم بهتر

در Dijkstra می‌توان Min-Heap داشت تا ارزان‌ترین Node مرزی سریع انتخاب شود.

پیاده‌سازی خوانا با JavaScriptJavaScript

class MinHeap {
  data = [];
  push(value) {
    this.data.push(value);
    let i = this.data.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
}

این کد را چطور بخوانی؟

syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.

پیچیدگی

peek O(1), insert/remove O(log n)

این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.

چه زمانی استفاده کنیم؟

موارد مناسب

وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.

اشتباهات رایج

کجا معمولاً اشتباه می‌کنیم؟

پیچیدگی را بدون فهم representation حفظ نکن.
بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.

در مصاحبه چطور توضیح بدهیم؟

مدل یک پاسخ حرفه‌ای

نگو Heap یک درخت مرتب است. نکته اصلی دسترسی O(1) به عنصر با بیشترین/کمترین اولویت و insert/remove حدود O(log n) است.

مسئله→ایده اصلی→Invariant / State→Big-O→Trade-off

چند سؤال مصاحبه‌ای سریع

هیپ چه مسئله‌ای را حل می‌کند؟

درباره Complexity چه چیزی باید بگویم؟

پیچیدگی معمول اینجا peek O(1), insert/remove O(log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.

رایج‌ترین اشتباه چیست؟

پیچیدگی را بدون فهم representation حفظ نکن.

موضوعات مرتبط برای ادامه مطالعهصف اولویتHeap SortDijkstra

class MinHeap { data = []; push(value) { this.data.push(value); let i = this.data.length - 1; while (i > 0) { const p = Math.floor((i - 1) / 2); if (this.data[p] <= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } } }