Heap و Priority Queuecomplete tree in an array · sift-up · sift-down · heapify · top k · two heaps

الـ heap بتديك أصغر عنصر (أو أكبر عنصر) في O(1)، وبتضيف وتشيل في O(log n) مضمونة. هي tree، بس متخزّنة في array عادية من غير ولا pointer، والقاعدة بتاعتها أضعف من الـ BST بكتير، وده بالظبط سر سرعتها.

قبله: Binary Search Tree و Binary Trees بيمهّد لـ: Graphs و Dijkstra في Graphs المتقدمة

هتطلع من الفصل ده وإنت عارف

  • إزاي tree كاملة تتخزّن في array، وليه الأب عند (i - 1) >> 1 والأولاد عند 2i + 1 و 2i + 2.
  • الـ sift-up والـ sift-down خطوة بخطوة، وليه بنبدّل مع الابن الأصغر بالذات.
  • تكتب class اسمها MinHeap بـ comparator في 5 دقايق من دماغك، لأن JS مفيهاش heap جاهزة.
  • ليه الـ heapify بياخد O(n) مش O(n log n).
  • تحل Kth Largest و Last Stone و K Closest و Top K Frequent و Merge k Lists و Find Median، وتعرف ليه "أكبر k" محتاجة min-heap.

ليه Heap؟

في الفصل اللي فات الـ BST كانت مترتبة بالكامل، وده كان ليه تمن: كل عملية O(h)، والـ tree ممكن تميل. دلوقتي السؤال: لو كل اللي محتاجه هو أصغر عنصر بس؟

فيه نوع مسائل بيتكرر كتير: عناصر بتدخل طول الوقت، وكل شوية عايز أصغر واحد (أو أهم واحد) وتشيله. مثلًا: مهام بأولويات، أوردرات بأسعار، أقصر مسافة لحد دلوقتي في Dijkstra. تعالى نجرّب الأدوات اللي تعرفها:

الأداةتضيفتبص على الأصغرتشيل الأصغرالمشكلة
array عاديةO(1)O(n)O(n)كل سؤال بيلف على كله
sorted arrayO(n)O(1)O(1)كل إضافة بتزق عناصر
تعمل sort كل مرةO(1)O(n log n)O(n log n)أسوأ حاجة فيهم
BSTO(h)O(h)O(h)ممكن تميل فتبقى O(n)
HeapO(log n)O(1)O(log n)مضمونة دايمًا، بس مش بتدوّر على أي عنصر

الـ heap هي الأداة اللي معمولة للسؤال ده بالظبط. والـ priority queue هو الاسم بتاع الفكرة: queue بتطلّع الأهم الأول مش اللي جه الأول. والـ heap هي الطريقة المشهورة اللي بنعمل بيها الـ priority queue. في الكلام هتسمع الاسمين كأنهم حاجة واحدة.

تشبيه الطوارئ في مستشفى. الدكتور مش بيكشف بالدور. الحالة الأخطر بتدخل الأول، حتى لو جت آخر واحدة. والممرضة مش محتاجة ترتّب كل اللي في الصالة من الأخطر للأخف، كفاية تعرف مين الأخطر دلوقتي. ده بالظبط اللي الـ heap بتعمله: مش مترتبة كلها، بس الأهم دايمًا فوق.

بص على heap صغيرة. هنضيف 6 أرقام، وبعدين نشيل أصغر واحد 3 مرات. الـ heap بتتعرض مرتين: tree فوق، ونفس الحاجة كـ array تحت:

لاحظ إن الـ array مش مترتبة، ومع كده أصغر رقم دايمًا في الخانة 0. ولاحظ إن كل pop طلّع الأصغر اللي فاضل، فالأرقام بتطلع مترتبة. ده اسمه heap sort لو عملته على كله.

طب إزاي تعرف من كلام المسألة إنها محتاجة heap؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

لما تشوف: kth largest / smallesttop kk closestk most frequent merge k sortedmedian of a streamrepeatedly take the biggest two schedule by prioritycheapest nextshortest path with weights
ومش هو غالبًا لو: محتاج الأصغر مرة واحدة بسsliding window maximumkth smallest in a BSTكل الداتا موجودة ومحتاجها مترتبة كلها

لو محتاج الأصغر مرة واحدة، loop عادية بـ Math.min O(n) وخلاص. لو كل الداتا قدامك ومحتاجها كلها مترتبة، sort مرة واحدة أسهل. الـ heap بتكسب لما الإضافة والشيل متداخلين، أو لما محتاج أحسن k بس من كتير. والـ sliding window maximum ليها أداة أحسن، الـ deque، في فصل الـ queue.

الشكلالفكرةالـ complexityمسائل
Top kheap حجمها k، اللي فوق هو "البوّاب" اللي بيتشال أول واحدO(n log k)Kth Largest، K Closest، Top K Frequent
Simulationكل خطوة خد الأهم، واعمل حاجة، ورجّع الناتجO(n log n)Last Stone Weight، Task Scheduler
K-way mergeheap فيها أول عنصر من كل listO(N log k)Merge k Sorted Lists، Kth in Sorted Matrix
Two heapsmax-heap للنص الصغير، min-heap للنص الكبيرO(log n) لكل إضافةFind Median from Data Stream
flowchart TD
  A["Need the best element again and again?"] -- no --> N["One pass with min / max, or sort once"]
  A -- yes --> B{"Only the best k matter?"}
  B -- yes --> K["Heap of size k: the top is the one to kick out"]
  B -- no --> C{"Merging many sorted lists?"}
  C -- yes --> M["Heap of the current heads"]
  C -- no --> D{"Need the middle, not the edge?"}
  D -- yes --> T["Two heaps: max-heap low half, min-heap high half"]
  D -- no --> S["One heap: push, pop the best, push results back"]
  

اسأل نفسك الأسئلة دي بالترتيب ده.

قبل ما نستخدمها، لازم نفهم هي متخزّنة إزاي، لأن ده سر سرعتها.

الـ heap: complete tree متخزّنة في array

الـ heap (وهنبدأ بالـ min-heap) هي binary tree فيها شرطين:

  1. الشكل (complete): كل المستويات مليانة على الآخر، ما عدا آخر مستوى ممكن يكون ناقص، بس بيتملي من الشمال لليمين من غير فراغات. يعني الـ tree دايمًا متوازنة: لو فيها n عنصر، الـ height حوالي log₂ n.
  2. الترتيب (heap property): كل أب أصغر من أو يساوي أولاده. وبس. مفيش أي شرط بين الأخين، ولا بين الشمال واليمين.

من الشرط التاني: الأب أصغر من أولاده، وأولاده أصغر من أولادهم، وهكذا. يبقى الـ root أصغر من الكل. وده كل اللي محتاجينه.

الفرق عن الـ BST الـ BST قاعدتها على كل الـ subtree وبين الشمال واليمين، فهي مترتبة بالكامل وتقدر تدوّر فيها. الـ heap قاعدتها بين الأب وأولاده بس (والشرط ده لوحده بيوصل لكل اللي تحت)، فمش مترتبة، ومش هتعرف تدوّر فيها على 7 مثلًا من غير ما تلف على كله. اللي بتكسبه: الشكل بيفضل complete دايمًا، فالـ height log n مضمون، والـ tree تتخزّن في array.

ليه array؟ ومنين جت المعادلات؟

رقّم الـ nodes مستوى مستوى، من فوق لتحت ومن الشمال لليمين: الـ root رقم 0، ولاده 1 و 2، ولادهم 3 و 4 و 5 و 6، وهكذا. عشان الـ tree complete مفيش فراغات، فكل رقم من 0 لـ n - 1 ليه node، والأرقام دي بالظبط indices في array.

طب أولاد node رقم i فين؟ كل node قبل i (من 0 لـ i - 1، يعني i nodes) ليها اتنين أولاد، وأولادهم بييجوا قبل أولاد i في الترقيم، وبيبدأوا من index 1 (لأن 0 هو الـ root). يعني الأولاد دول واخدين الأماكن من 1 لـ 2i. فأولاد i بيبدأوا عند 2i + 1، وبعده 2i + 2. والأب بالعكس: لو إنت عند i، أبوك هو floor((i - 1) / 2). جرّب: الـ 5 والـ 6 أبوهم floor(4 / 2) = 2 و floor(5 / 2) = 2.

  1. x >> 1 بيزق الـ bits خانة لليمين، يعني قسمة على 2 وترمي الكسر (التفاصيل في فصل الـ bits). من غير floor، i = 4 هتدّيك 1.5، و h[1.5] بـ undefined من غير أي error.
  2. الأولاد. ممكن يطلعوا برا الـ array: لو 2 * i + 1 >= h.length يبقى الـ node دي leaf. أي كود بيستخدم left(i) لازم يشيّك ده الأول.
  3. نبدأ من 1 لأن الـ root (index 0) مالوش أب. لو بدأت من 0، parent(0) هتطلع -1، و h[-1] بـ undefined.
  4. بنشيّك كل node مع أبوها. كل علاقة أب وابن بتتشيّك مرة واحدة بالظبط، فالـ check ده O(n). لو كله تمام، يبقى min-heap.

شوف نفس الـ heap كـ tree وكـ array. الرقم بين القوسين تحت كل node هو الـ index بتاعها في الـ array:

طب لو ضفنا رقم جديد، إزاي القاعدة تفضل ماشية؟

الـ push: حطه في الآخر، وطلّعه لفوق (sift-up)

عايزين نضيف رقم. عندنا شرطين لازم يفضلوا صح: الشكل والترتيب.

  1. الشكل: المكان الوحيد اللي يخلّي الـ tree لسه complete هو أول خانة فاضية في آخر مستوى، وده آخر الـ array. فبنعمل h.push(x) عادي.
  2. الترتيب: كل حاجة كانت heap قبل كده، فالمكان الوحيد اللي ممكن يبقى فيه مشكلة هو بين الرقم الجديد وأبوه. لو الجديد أصغر من أبوه، نبدّلهم. دلوقتي ممكن يبقى أصغر من جدّه، فنكرر. ونقف لما أبوه يبقى أصغر منه أو يساويه، أو لما يوصل للـ root.
  3. ليه التبديل مش بيبوّظ حاجة تحت؟ الأب اللي نزل كان أصغر من أو بيساوي كل اللي تحته (ده كان heap)، والمكان اللي نزل فيه جوه نفس الـ subtree، فهو لسه أصغر من كل اللي تحته. والجديد اللي طلع أصغر من الأب، والأب كان أصغر من أخوه التاني، فالجديد أصغر من الأخ برضه.
  1. الرقم بيدخل في آخر الـ array، يعني آخر مكان في آخر مستوى. الشكل اتحل في سطر واحد.
  2. i هو مكان الرقم الجديد دلوقتي، وهيتحرك معاه. h.length - 1 لأن الـ push زوّد الطول خلاص، والـ index الأخير هو الطول ناقص 1.
  3. ليه i > 0 مش i >= 0؟ لما i = 0 يبقى وصلنا للـ root، ومالوش أب نقارن بيه. لو كتبت >= 0، هتحسب p = -1 وتقارن بـ h[-1].
  4. أب الـ i، بنفس المعادلة اللي فوق.
  5. ليه <=؟ لو الأب بيساوي الجديد، القاعدة متحققة ومفيش داعي نبدّل. والـ break ده early exit: اللي فوق كان heap أصلًا، فمش محتاجين نكمّل.
  6. التبديل بالـ destructuring: الطرف اليمين بيتحسب الأول كـ array مؤقتة، وبعدين بيتوزع. بديل للـ temp التقليدي.
  7. الرقم بقى في مكان أبوه، فنكمّل من هناك. كل لفة بتطلع مستوى، والـ height حوالي log n، فالـ push كله O(log n).

هنضيف 1 (هيطلع لحد الـ root)، وبعدين 7 (هيطلع خطوة ويقف):

الإضافة طلّعت الرقم لفوق. الشيل بيعمل العكس: بينزّل رقم لتحت.

الـ pop: خد الـ root، وحط الأخير مكانه ونزّله (sift-down)

أصغر رقم في الـ root، فده اللي هنرجّعه. بس لو شلناه، هيبقى فيه فتحة فوق. الحل:

  1. الشكل: العنصر الوحيد اللي نقدر نشيله والـ tree تفضل complete هو آخر عنصر في الـ array. فنشيله بـ h.pop()، ونحطه مكان الـ root.
  2. الترتيب: الرقم ده جاي من تحت خالص، فغالبًا كبير. نقارنه بأولاده: لو أكبر من أي واحد فيهم، نبدّله مع الأصغر فيهم، ونكرر لحد ما يبقى أصغر من الاتنين أو يوصل leaf.
  3. ليه مع الأصغر بالذات؟ اللي هيطلع فوق هيبقى أب للابن التاني. لو طلّعنا الأكبر، هيبقى أب لابن أصغر منه، والقاعدة اتكسرت. الأصغر هو الوحيد اللي ينفع يبقى أب للاتنين.
تشبيه مدير الشركة استقال. بدل ما نعيد الهيكل كله، بنقعّد آخر واحد اتعيّن على كرسي المدير مؤقتًا، وبعدين بنقارنه بأقوى اتنين تحته: لو واحد منهم أحسن منه، أحسنهم ياخد الكرسي وهو ينزل مكانه. ويفضل ينزل لحد ما يلاقي مستواه.
  1. heap فاضية، مفيش حاجة نرجّعها. بنرجّع undefined زي [].pop().
  2. بنحفظ الإجابة قبل ما نلمس أي حاجة، لأن الـ h[0] هيتكتب عليه بعد سطرين.
  3. بنشيل آخر عنصر. ده O(1)، بعكس h.shift() اللي بتشيل الأول وتزق كل الباقي O(n).
  4. أهم شرط في الدالة. لو الـ heap كان فيها عنصر واحد، الـ h.pop() شاله وبقت فاضية. لو كتبنا h[0] = last من غير الشرط ده، هنرجّع العنصر تاني، والـ heap عمرها ما هتفضى.
  5. الأخير بقى في الـ root، و i ماشي معاه.
  6. أولاد i. ممكن يكونوا برا الـ array، وده بنشيّكه في السطرين الجايين.
  7. small هو "أصغر واحد من التلاتة": i وأولاده. بنبدأ بافتراض إن i نفسه هو الأصغر.
  8. ليه l < h.length الأول؟ لو الابن مش موجود، الـ && بتقف قبل ما تقرا h[l]. وخلي بالك: السطر 12 بيقارن بـ h[small] مش h[i]، عشان نختار الأصغر من الابنين، مش أول واحد أصغر من الأب.
  9. لو i نفسه أصغر من أولاده (أو مالوش أولاد)، يبقى وصل لمكانه.
  10. نبدّله مع الابن الأصغر وننزل معاه. كل لفة بتنزل مستوى، فالـ pop كله O(log n).
  11. بنرجّع الأصغر اللي حفظناه في السطر 3.

هنعمل pop مرتين من الـ heap اللي طلعت من الـ push فوق:

الدالتين دول شغالين على أرقام بس. المسائل الحقيقية فيها أزواج ونقط و nodes، وساعات max-heap.

الـ class: MinHeap بـ comparator

الدالتين اللي فوق شغالين على أرقام بس، ومع <. في المسائل الحقيقية هتحط في الـ heap أزواج [value, freq]، أو نقط [x, y]، أو list nodes، وساعات هتحتاج max-heap. الحل: comparator، بنفس فكرة الـ comparator بتاع sort اللي في فصل الـ sorting.

عقد الـ comparator compare(a, b) بيرجّع رقم. سالب يعني a لازم يبقى فوق b. موجب يعني b فوق. صفر يعني مش فارقة. الـ default (a, b) => a - b بيدّي min-heap. والـ (a, b) => b - a بيقلبها max-heap من غير ما تغيّر سطر في الـ class.
  1. الاسم MinHeap معناه: اللي الـ comparator بيقول عليه "أصغر" بيطلع فوق. لو بعتّله comparator مقلوب، هيشتغل max-heap. ممكن تسميها Heap بس، بس MinHeap بتفكّرك بالـ default.
  2. default parameter: لو ما بعتّش comparator، يبقى أرقام عادية والأصغر فوق. لازم يرجّع رقم مش boolean. (a, b) => a < b بترجّع true أو false، والـ class بتقارن النتيجة بـ < 0، والـ boolean عمره ما هيبقى أقل من صفر، فالـ heap مش هتترتب خالص.
  3. الـ array اللي فيها الـ tree، والـ comparator. الاتنين على this عشان كل الـ methods تشوفهم.
  4. size و peek الاتنين O(1). الـ peek بيرجّع الأهم من غير ما يشيله.
  5. نفس الـ push اللي فوق: في الآخر، وبعدين sift-up من آخر index.
  6. نفس الـ pop اللي فوق بالظبط، والـ sift-down اتنقل لـ method لوحده. السطر 17 هو نفس الشرط المهم بتاع "العنصر الوحيد".
  7. بدل h[p] <= h[i] بقت compare(d[i], d[p]) >= 0، ومعناها: الابن مش لازم يبقى فوق أبوه. خلي بالك من ترتيب الـ arguments: الابن الأول والأب التاني، يعني "هل الابن ينفع يبقى فوق الأب؟".
  8. نفس الـ sift-down، والمقارنة بقت compare(d[l], d[best]) < 0: "الابن ده لازم يبقى فوق أحسن واحد لحد دلوقتي؟". سمّيناه best بدل small لأنه في max-heap هيبقى الأكبر.
في الانترفيو لو المسألة محتاجة heap في JS، قول للـ interviewer: "JS مفيهاش priority queue built-in، فهكتب heap صغيرة". واكتب الـ class دي في 5 دقايق. احفظها لحد ما تكتبها من غير تفكير: 44 سطر، وكلهم مفهومين. ساعات الـ interviewer هيقولك "افترض إن عندك heap جاهزة"، وده أحسن، بس ما تعتمدش عليه.

لو عندك الأرقام كلها من الأول، فيه طريقة أسرع من إنك تعمل push لكل واحد.

Heapify: تحوّل array كاملة لـ heap في O(n)

لو عندك n رقم من الأول، ممكن تعمل push لكل واحد: n مرة × O(log n) = O(n log n). بس فيه طريقة أسرع: سيب الأرقام في مكانها، وصلّح الـ tree من تحت لفوق.

  1. الـ leaves heaps جاهزة: node لوحدها مفيهاش أي أب وابن يتخانقوا. ونص الـ array تقريبًا leaves: كل index من n >> 1 لآخر الـ array ملوش أولاد، لأن 2i + 1 >= n.
  2. نمشي بالعكس: من آخر أب ((n >> 1) - 1) لحد الـ root، ونعمل sift-down لكل واحد. ليه بالعكس؟ لأن الـ sift-down محتاج إن أولاد الـ node يكونوا heaps، ولما بنمشي من تحت، بنكون صلّحنا الأولاد قبل الأب.
  3. ليه O(n) مش O(n log n)؟ الـ sift-down بياخد على قد ارتفاع الـ node من تحت، مش على قد الـ height كله. ونص الـ nodes (الـ leaves) شغلهم صفر. ربعهم بيتحركوا خطوة بالكتير. التُمن خطوتين. وهكذا. المجموع n/4 × 1 + n/8 × 2 + n/16 × 3 + ... وده أقل من n. الـ nodes الكتير شغلها قليل، والشغل الكتير لـ nodes قليلة فوق.
المستوى من تحتعدد الـ nodes (تقريبًا)أقصى نزول لكل nodeالشغل
الـ leavesn / 200
فوقهمn / 41n / 4
فوقهمn / 82n / 4
فوقهمn / 1633n / 16
.........المجموع أقل من n
  1. (h.length >> 1) - 1 هو آخر index ليه ابن: مع n = 7 ده 2، وأولاده 5 و 6. و i >= 0 بالـ = عشان الـ root لازم يتصلّح هو كمان.
  2. لحظة ما نوصل لـ i، كل الـ indices الأكبر منه اتصلّحت، يعني أولاده heaps. فالـ sift-down هنا صح.
  3. نفس الـ sift-down اللي في الـ pop بالظبط، بس بيبدأ من أي i.

في الانترفيو، push لكل عنصر (O(n log n)) مقبول في 99% من المسائل. اعرف الـ heapify عشان سؤال "تقدر أسرع؟"، وعشان لو اتسألت "الـ heapify complexity كام؟" تقول O(n) وتشرح ليه.

فاضل سؤال: ليه أصلًا لازم نكتب كل ده بإيدنا في JS؟

ليه JS مفيهاش priority queue؟

الـ standard library بتاعة JS صغيرة جدًا بالمقارنة بلغات تانية. فيها Array و Map و Set وبس تقريبًا. مفيش heap، ولا queue سريعة، ولا sorted set. اللجنة اللي بتطوّر اللغة بتضيف حاجات ببطء، والـ JS اتعملت أصلًا للمتصفح مش للخوارزميات.

اللغةالأداةالـ default
Pythonheapqmin-heap على list عادية
JavaPriorityQueuemin-heap
C++std::priority_queuemax-heap. للـ min استخدم greater<int>
JavaScriptمفيشاكتبها بإيدك

LeetCode بيحط مكتبة اسمها @datastructures-js/priority-queue في بيئة الـ JS بتاعته (فيها MinPriorityQueue و MaxPriorityQueue)، بس الـ API بتاعها اتغيّر بين النسخ، وفي انترفيو حقيقي أو موقع تاني مش هتلاقيها. فالأضمن إنك تعرف تكتب الـ class بنفسك.

الحل اللي بيغري: sort كل مرة arr.push(x); arr.sort((a, b) => a - b); بيشتغل، وفي مسائل صغيرة بيعدّي. بس كل push بقى O(n log n). مع 10⁵ عملية ده حوالي 10¹⁰ عملية: TLE أكيد. لو المسألة فيها إضافة وشيل متداخلين، الـ heap مش رفاهية.

كده الـ class جاهزة. يلا نستخدمها، ونبدأ بأشهر pattern: أحسن k.

مثال محلول 1: Kth Largest Element in an Array

Kth Largest Element in an Array

mediumLeetCode 215

رجّع العنصر رقم k من ناحية الكبير. يعني لو رتّبت الـ array تنازلي، العنصر اللي في المكان رقم k (والمتكرر بيتحسب كل مرة).

Input: nums = [7, 2, 9, 4, 1, 8, 5], k = 3 Output: 7 (descending: 9, 8, 7, ...) Input: nums = [3, 3, 3], k = 2 Output: 3 (duplicates count)

نفكّر فيها مع بعض

  1. أول حل: رتّب تنازلي ورجّع nums[k - 1]. ده O(n log n)، وصح، وفي الانترفيو قوله الأول. بس الـ interviewer هيسأل "تقدر أحسن؟" أو "لو الأرقام جاية stream مش عارف آخرها؟".
  2. محتاجين إيه بالظبط؟ مش محتاجين الترتيب كله. محتاجين نعرف أكبر k رقم، وأضعف واحد فيهم هو الإجابة.
  3. الـ key insight: نعمل "نادي" فيه k كراسي بس، فيه أكبر k رقم شفناهم لحد دلوقتي. أي رقم جديد بييجي، بنقارنه بـ أضعف عضو في النادي (الأصغر فيهم). لو الجديد أكبر، الأضعف يطلع والجديد يدخل.
  4. ليه min-heap مش max-heap؟ لأن اللي محتاجين نوصله بسرعة ونشيله هو الأصغر في النادي، مش الأكبر. الـ min-heap بتحط الأصغر فوق. وبعد ما نلف على كله، النادي فيه أكبر k، والـ peek هو أصغرهم، يعني الـ kth largest بالظبط.
  5. الحالات الطرفية: k = 1 (أكبر رقم)، k = n (أصغر رقم)، أرقام متكررة، أرقام سالبة.
تشبيه نادي فيه 3 كراسي بس، والبوّاب واقف جنب أضعف واحد قاعد. كل ما حد جديد ييجي، البوّاب يقارنه بالأضعف ده. لو الجديد أقوى، الأضعف يطلع برا. في الآخر، اللي قاعدين هما أقوى 3، والبوّاب واقف جنب تالت أقوى واحد. الـ min-heap هي البوّاب: دايمًا عارف مين الأضعف.
  1. min-heap بالـ comparator الـ default. الـ heap دي عمرها ما هتعدّي k + 1 عنصر.
  2. كل رقم بيدخل النادي الأول. حتى لو صغير، هيطلع في السطر الجاي.
  3. ليه > k مش >= k؟ عايزين النادي فيه k بالظبط. مع >= k هتشيل وهم k فيبقوا k - 1، وترجّع الإجابة الغلط. جرّبها في دماغك بـ k = 1.
  4. أصغر واحد في أكبر k. الـ peek مش pop، مش محتاجين نشيله.

التعقيد: كل رقم بيعمل push و pop على heap حجمها k، فالوقت O(n log k)، والـ memory O(k). لو k صغير جدًا (زي 3)، ده تقريبًا O(n). ولو k = n، بيبقى O(n log n) زي الـ sort.

حلول تانية تتقال Max-heap للكل: heapify على كله O(n)، وبعدين pop k - 1 مرة O(k log n). صح، بس memory O(n) ومش بيشتغل على stream. Quickselect: فكرة الـ quicksort بس بتنزل ناحية واحدة، متوسطها O(n) وأسوأها O(n²). اذكره كـ follow-up، بس الـ heap هو اللي متوقع تكتبه.

هنا كان الـ min-heap كفاية. طب لو محتاج الأكبر كل مرة، والناتج بيرجع يتنافس تاني؟

مثال محلول 2: Last Stone Weight

Last Stone Weight

easyLeetCode 1046

عندك حجارة بأوزان. كل دور خد أتقل حجرين وخبطهم ببعض: لو وزنهم واحد الاتنين بيختفوا، ولو مختلفين التقيل بيفضل منه الفرق. كمّل لحد ما يفضل حجر واحد أو مفيش. رجّع وزن الأخير، أو 0.

Input: stones = [6, 3, 9, 2, 5] Output: 1 Input: stones = [4, 4] Output: 0

نفكّر فيها مع بعض

  1. الجديد هنا: max-heap بالـ comparator المقلوب، والناتج بيرجع الـ heap تاني. ده pattern اسمه simulation.
  2. Simulation: المسألة بتقولك تعمل إيه بالظبط، مفيش حيلة. السؤال بس: إزاي تجيب أتقل اتنين بسرعة كل دور؟
  3. Brute force: رتّب كل دور. n دور × O(n log n) = O(n² log n). مع 30 حجر (الـ constraint) هيعدّي، بس الـ heap هو المقصود.
  4. الفكرة: "أتقل حاجة" كل شوية، والفرق بيرجع يتحط تاني. ده max-heap: نفس الـ class بـ comparator مقلوب.
  5. الحالات الطرفية: حجر واحد من الأول (يرجع هو)، كل الحجارة بتختفي (يرجع 0).
  1. b - a: لو b أكبر، الناتج موجب، يعني b فوق. فالأكبر بيطلع فوق. ده الـ max-heap كله، من غير ما نكتب class تانية.
  2. push لكل حجر، O(n log n). ممكن heapify في O(n) بس مش فارقة هنا.
  3. ليه > 1؟ محتاجين حجرين عشان نخبطهم. لو فاضل واحد أو صفر نقف. لو كتبت > 0، أول ما يفضل حجر واحد هتعمل pop مرتين، والتانية هترجع undefined.
  4. الأول اللي يطلع هو الأتقل، فـ y >= x مضمونة، والفرق y - x عمره ما هيبقى سالب.
  5. لو متساويين، الاتنين اختفوا ومفيش push. لو لأ، الباقي يرجع الـ heap ويتنافس من جديد.
  6. لو فاضل حجر، وزنه هو الإجابة. لو الـ heap فاضية، 0.

التعقيد: كل دور بيقلل عدد الحجارة واحد على الأقل، فعدد الأدوار أقل من n، وكل دور O(log n). المجموع O(n log n) والـ memory O(n).

طب لو عايز أصغر k مش أكبر k، والعناصر نقط مش أرقام؟

مثال محلول 3: K Closest Points to Origin

K Closest Points to Origin

mediumLeetCode 973

عندك نقط [x, y]. رجّع أقرب k نقط لنقطة الأصل (0, 0)، بأي ترتيب.

Input: points = [[1,3],[-2,2],[2,-1],[0,4],[-1,-1]], k = 2 Output: [[2,-1],[-1,-1]] (squared distances: 10, 8, 5, 16, 2)

نفكّر فيها مع بعض

  1. الجديد هنا: نفس نادي 215، بس عايزين الأصغر k، والعناصر arrays مش أرقام.
  2. المسافة: sqrt(x² + y²). بس إحنا بنقارن مسافات بس، والـ sqrt بتحافظ على الترتيب (لو a² < b² يبقى a < b للموجب). فنقارن x² + y² على طول، من غير sqrt، ومن غير كسور.
  3. نفس فكرة النادي: عايزين أقرب k. النادي فيه k نقط، والبوّاب واقف جنب أضعف واحد، وهنا الأضعف هو الأبعد. فالـ heap لازم تطلّع الأبعد فوق: max-heap بالمسافة.
  4. القاعدة اللي تحفظها: نوع الـ heap عكس اللي بتحتفظ بيه. عايز أكبر k؟ min-heap. عايز أصغر k (أقرب k)؟ max-heap. لأن الـ heap فوقها اللي هيتطرد.
  5. الحالات الطرفية: k = n (رجّع كله)، نقطتين بنفس المسافة (أي واحدة تنفع).
  1. المسافة المربعة. مع الـ constraints (إحداثيات لحد 10⁴) أكبر قيمة 2 × 10⁸، بعيد جدًا عن حدود الأرقام في JS.
  2. dist(b) - dist(a) مقلوبة، فالأبعد فوق. الـ heap فيها النقط نفسها (arrays)، والـ comparator هو اللي بيعرف يقارنها.
  3. نفس سطرين الـ 215 بالظبط. الـ pop بيطرد الأبعد في النادي.
  4. المسألة بتقبل أي ترتيب، فبنرجّع الـ array الداخلية على طول. لو عايزهم مترتبين من الأقرب، اعمل pop لحد ما تفضى واقلب النتيجة.

تحت كل node النقطة نفسها، والرقم جوه الدايرة هو المسافة المربعة:

التعقيد: O(n log k) وقت و O(k) memory. والـ sort على المسافة O(n log n) حل مقبول برضه، قوله الأول.

لحد دلوقتي العناصر كانت جاهزة. طب لو لازم تحسبها الأول؟

مثال محلول 4: Top K Frequent Elements

Top K Frequent Elements

mediumLeetCode 347

رجّع الـ k أرقام اللي اتكرروا أكتر حاجة، بأي ترتيب. الإجابة مضمون إنها واحدة.

Input: nums = [5, 1, 5, 2, 5, 1, 3, 1, 1], k = 2 Output: [5, 1] (1 appears 4 times, 5 appears 3 times)

نفكّر فيها مع بعض

  1. الجديد هنا: العناصر مش جاهزة. بنبنيها الأول (Map للعدّ)، وبعدين نفس النادي على أزواج [value, freq].
  2. خطوة 1: نعدّ. Map من الرقم لعدد مراته، زي ما اتعلمت في فصل الـ hashing. O(n).
  3. خطوة 2: أكبر k في العدد. دلوقتي عندنا أزواج [value, freq]، وعايزين أكبر k بالـ freq. ده 215 تاني بالظبط، بس على الـ freq: نادي فيه k، والبوّاب واقف جنب الأقل تكرار، يعني min-heap بالـ freq.
  4. ليه مش sort؟ الـ sort على كل الأزواج O(m log m) حيث m عدد الأرقام المختلفة. الـ heap O(m log k). الاتنين مقبولين، والـ heap أحسن لما k صغير.
  5. الحالات الطرفية: k بيساوي عدد الأرقام المختلفة (رجّع كلهم)، رقم واحد بس متكرر.
  1. العدّ. (count.get(x) || 0) عشان أول مرة الـ get بترجّع undefined، و undefined + 1 بـ NaN.
  2. الـ comparator بيقارن بالعنصر التاني ([1])، وده الـ freq. a[1] - b[1] مش مقلوبة، فالأقل تكرار فوق.
  3. اللف على Map بـ for...of بيدّيك [key, value] في كل لفة، بنفس ترتيب الإضافة.
  4. نفس سطرين النادي.
  5. الـ heap فيها أزواج، والمطلوب الأرقام بس، فبناخد e[0] من كل زوج.

الـ node مكتوب فيها value×freq، يعني 5×3 معناها الرقم 5 اتكرر 3 مرات:

التعقيد: العدّ O(n)، والـ heap O(m log k). المجموع O(n + m log k)، والـ memory O(m). فيه حل O(n) بالـ bucket sort (array مكان كل index فيها عدد التكرار)، اذكره لو اتسألت "تقدر أسرع؟".

كل اللي فات الـ heap كانت بتمسك أحسن k. في المثال الجاي بتمسك حاجة تانية خالص: رأس كل list.

مثال محلول 5: Merge k Sorted Lists

Merge k Sorted Lists

hardLeetCode 23

عندك k linked lists، كل واحدة مترتبة تصاعدي. ادمجهم في linked list واحدة مترتبة.

Input: lists = [[1,4,7],[2,5],[3,6,8]] Output: [1,2,3,4,5,6,7,8]

تذكير من فصل الـ linked list: كل node فيها val و next، والـ dummy node هي node وهمية بنحطها في الأول عشان ما نعملش حالة خاصة لأول عنصر، وفي الآخر بنرجّع dummy.next.

نفكّر فيها مع بعض

  1. الجديد هنا: الـ heap مش بتمسك "أحسن k"، بتمسك مرشح واحد من كل list، وكل ما واحد يطلع اللي وراه يدخل.
  2. Brute force: لم كل القيم في array، رتّب، وابني list جديدة. O(N log N) حيث N مجموع كل العناصر. شغال، بس مش مستغل إن كل list مترتبة.
  3. دمج واحدة واحدة: ادمج الأولى مع التانية، والنتيجة مع التالتة... كل دمج بيلف على كل اللي اتجمع لحد دلوقتي، فالمجموع حوالي O(N × k).
  4. الفكرة: العنصر الجاي في النتيجة أكيد واحد من رؤوس الـ lists (أول عنصر لسه ما اتاخدش في كل list)، لأن كل list مترتبة. يعني في كل لحظة عندنا k مرشحين بس. نحطهم في min-heap، ونطلّع الأصغر، ونحط مكانه اللي بعده في نفس الـ list.
  5. ليه ده صح؟ اللي بعده في نفس الـ list هو المرشح الجديد الوحيد. كل الـ lists التانية رؤوسها ما اتغيرتش.
  6. الحالات الطرفية: lists = []، list فاضية جوه الـ lists (null)، list واحدة بس.
  1. الـ heap فيها nodes مش أرقام، والـ comparator بيقارن بالـ val. ميزة إننا بنحط الـ node نفسها: بنعرف اللي بعدها من node.next من غير ما نشيل رقم الـ list.
  2. ليه head !== null؟ الـ lists ممكن يكون فيها list فاضية. لو حطيت null في الـ heap، الـ comparator هيقرا null.val ويضرب error.
  3. الـ dummy والـ tail. الـ tail دايمًا آخر node في النتيجة.
  4. طول ما فيه مرشحين، الأصغر فيهم هو الجاي في الترتيب.
  5. نعلّقه في آخر النتيجة ونحرّك الـ tail. مش بنعمل nodes جديدة، بنعيد ربط الموجودين.
  6. اللي بعده في نفس الـ list ياخد مكانه كمرشح. لو الـ list خلصت، الـ heap بتصغر واحد.
  7. أول node حقيقية. ولو كل الـ lists فاضية، dummy.next بـ null، وده الصح.

التعقيد: كل عنصر من الـ N بيدخل الـ heap مرة ويطلع مرة، والـ heap عمرها ما بتعدّي k. يعني O(N log k) وقت و O(k) memory. لو k = 10⁴ و N = 10⁴، ده أسرع كتير من O(N × k).

في الانترفيو المسألة دي hard، بس الحل قصير. اللي بيفرق إنك تقول الفكرة بوضوح: "العنصر الجاي لازم يكون من الرؤوس، فهحط الرؤوس في heap". وبعدين اذكر الـ complexity وقارنها بالدمج واحدة واحدة.

آخر مثال: مش أكبر ولا أصغر، عايزين اللي في النص. heap واحدة مش كفاية.

مثال محلول 6: Find Median from Data Stream

Find Median from Data Stream

hardLeetCode 295

اعمل class فيها addNum(num) بتضيف رقم، و findMedian() بترجّع الـ median لكل اللي اتضاف لحد دلوقتي. الـ median هو اللي في النص بعد الترتيب، ولو العدد زوجي يبقى متوسط اللي في النص.

addNum(5) → findMedian() = 5 [5] addNum(15) → findMedian() = 10 [5, 15] addNum(1) → findMedian() = 5 [1, 5, 15] addNum(3) → findMedian() = 4 [1, 3, 5, 15]

نفكّر فيها مع بعض

  1. الجديد هنا: heap اتنين شغالين مع بعض، واحدة max وواحدة min.
  2. Brute force: array مترتبة، وكل إضافة تحطها في مكانها (binary search على المكان، وبعدين splice). الـ splice بيزق العناصر، فكل إضافة O(n).
  3. الـ median محتاج إيه؟ مش محتاج الترتيب كله. محتاج أكبر واحد في النص الصغير وأصغر واحد في النص الكبير. الاتنين دول اللي في النص.
  4. الفكرة: نقسم الأرقام نصين. النص الصغير في max-heap اسمها low (فوقها أكبر الصغيرين). النص الكبير في min-heap اسمها high (فوقها أصغر الكبار). ونحافظ على شرطين: كل اللي في low أصغر من أو يساوي كل اللي في high، و low يا قد high يا أكبر منها بواحد.
  5. الـ median: لو low أكبر بواحد، العدد فردي والـ median هو low.peek(). لو متساويين، متوسط الـ peeks.
  6. الحيلة في الإضافة: كل رقم جديد يدخل low الأول، وبعدين أكبر واحد في low ينتقل لـ high. ده بيضمن شرط الترتيب من غير ما نقارن بإيدنا. وبعدين لو high بقت أكبر، نرجّع أصغر واحد فيها لـ low.
  1. low max-heap، فالـ peek بتاعها هو أكبر رقم في النص الصغير. ده اللي جنب النص على طول من الشمال.
  2. high min-heap، فالـ peek بتاعها أصغر رقم في النص الكبير، اللي جنب النص من اليمين.
  3. ليه low الأول وبعدين high؟ اللي بيطلع من low هو أكبر واحد فيها، فلما يروح high الـ invariant "كل low <= كل high" بيفضل صح، من غير ولا if.
  4. لو high بقت أكبر، نرجّع أصغرها لـ low. اخترنا إن low هي اللي تاخد الزيادة، فالـ median في العدد الفردي يبقى low.peek() دايمًا.
  5. عدد فردي: low فيها واحد زيادة، وأكبرها هو اللي في النص بالظبط.
  6. عدد زوجي: النص بين أكبر الصغيرين وأصغر الكبار. القسمة على 2 هنا عادية مش >> 1، لأن الـ median ممكن يبقى كسر زي 4.5، والـ >> بيرمي الكسر.

هنا محتاجين heap اتنين، والـ animation بتعرضهم كـ arrays (الـ array الداخلية لكل heap). الصف الأخير مش متخزّن في أي حتة، ده بس عشان تشوف الأرقام مترتبة والنصين جنب بعض:

التعقيد: كل addNum فيه 3 أو 5 عمليات heap، كل واحدة O(log n)، فهو O(log n). والـ findMedian O(1). الـ memory O(n).

شفت كام سطر ممكن يغلّطك في الـ heap؟ يلا نجمعهم.

غلطات مشهورة

الـ heap كود قصير، بس كل سطر فيه ممكن يتكتب غلط بطريقة بتعدّي من الـ examples الصغيرة. دي أشهرهم:

1. قسمة من غير floor في الأب

استخدم (i - 1) >> 1 أو Math.floor((i - 1) / 2). مع الـ indices الفردية القسمة بتطلع صح بالصدفة، فالغلطة بتظهر بعد كذا push بس.

2. في الـ sift-down تبدّل مع أول ابن أصغر، مش أصغر ابن

لازم السطرين يقارنوا بـ h[small] مش بـ h[i]، ومن غير else: الأول يختار الشمال لو أصغر من الأب، والتاني يختار اليمين لو أصغر من اللي اتختار لحد دلوقتي.

3. comparator بيرجّع boolean

الـ comparator لازم يرجّع رقم: (a, b) => a - b. نفس القاعدة بتاعة sort.

4. pop للعنصر الوحيد من غير الشرط

لازم if (d.length > 0) قبل ما ترجّع الأخير مكان الـ root.

5. نوع الـ heap غلط في الـ top k

اللي فوق الـ heap هو اللي بيتطرد. عايز تحتفظ بالأكبر؟ يبقى الأصغر هو اللي يتطرد، يعني min-heap. القاعدة: نوع الـ heap عكس اللي بتحتفظ بيه.

6. الـ priority_queue في C++ max مش min

لو بتحل بـ C++: priority_queue<int> pq; بتطلّع الأكبر. للـ min-heap: priority_queue<int, vector<int>, greater<int>> pq;. ناس كتير بتكتب Dijkstra بالـ default وتطلّع أطول طريق بدل أقصر طريق.

دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.

اختبر نفسك

في heap متخزّنة في array، الـ node اللي عند index 9: أبوها عند كام، وأولادها عند كام؟

  • أبوها 4، وأولادها 18 و 19
  • أبوها 4، وأولادها 19 و 20
  • أبوها 5، وأولادها 19 و 20
  • أبوها 4.5، وأولادها 18 و 19

الأب (9 - 1) >> 1 = 4. الأولاد 2 × 9 + 1 = 19 و 2 × 9 + 2 = 20. وتأكد بالعكس: (19 - 1) >> 1 = 9 و (20 - 1) >> 1 = 9.

أنهي جملة مش لازم تبقى صح في أي min-heap؟

  • أصغر عنصر في index 0
  • كل أب أصغر من أو يساوي أولاده
  • الـ array مترتبة تصاعدي
  • الـ height حوالي log n

الـ heap مش مترتبة. مثلًا [1, 5, 2] heap صح (1 أصغر من 5 ومن 2)، ومع كده 5 قبل 2. الشرط بين الأب وولاده بس، مش بين الإخوات.

في الـ sift-down، الأب 9 وولاده 3 و 1. نبدّله مع مين؟

  • مع 3، لأنه الشمال
  • مع 1، لأنه الأصغر
  • مع أي واحد فيهم
  • مع الاتنين بالترتيب

اللي هيطلع هيبقى أب للتاني. لو طلّعنا 3، هيبقى أب لـ 1 وهو أكبر منه: القاعدة اتكسرت. الأصغر بس هو اللي ينفع يبقى أب للاتنين.

Kth Largest بـ min-heap حجمها k على n رقم. الـ complexity كام؟

  • O(n)
  • O(n log k)
  • O(n log n)
  • O(k log n)

كل رقم من الـ n بيعمل push وساعات pop، والـ heap عمرها ما بتعدّي k + 1، فكل عملية O(log k).

ليه الـ heapify (sift-down من آخر أب لحد الـ root) بياخد O(n) مش O(n log n)؟

  • عشان بنعمل sift-down بس على نص العناصر، والنص ده O(n)
  • عشان أغلب الـ nodes قريبة من تحت ومش هتنزل غير خطوات قليلة، والمجموع أقل من n
  • عشان الـ sift-down O(1)
  • هو فعلًا O(n log n)

الإجابة الأولى ناقصة: نص العناصر × log n لسه O(n log n). اللي بيفرق إن ربع العناصر بتنزل خطوة واحدة بس، والتُمن خطوتين، وهكذا. الـ nodes اللي بتنزل كتير قليلة جدًا (الـ root واحد بس).

تمرين: فكّر قبل ما تفتح

Kth Largest Element in a Stream

easyLeetCode 703

اعمل class بتاخد k و array أولية. بعد كده كل add(val) بتضيف رقم وترجّع الـ kth largest لحد دلوقتي.

k = 2, nums = [6, 1, 9] add(3) → 6, add(7) → 7, add(10) → 9, add(2) → 9
تلميح 1

ده 215 بالظبط، بس الـ loop مش في دالة واحدة. الـ heap لازم تعيش بين النداءات، يعني تبقى property في الـ class.

تلميح 2

النادي (min-heap) حجمه k. الـ constructor يعمل add لكل رقم أولي. والـ add تعمل push، ولو الحجم عدّى k تعمل pop، وترجّع الـ peek.

الحل

كل add O(log k). لاحظ إن الـ array الأولية ممكن يكون فيها أقل من k عنصر، والـ > this.k بيتعامل مع ده لوحده: مش بنشيل غير لما يزيدوا. والمسألة بتضمن إن وقت ما تسأل يكون فيه k عناصر على الأقل.

لو الأسئلة عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

حلها بالترتيب ده. في كل مسألة الصق الـ MinHeap بتاعتك فوق الحل (أو اكتبها من دماغك، وده أحسن). لو قعدت أكتر من 25 دقيقة، ارجع للمثال المحلول اللي شبهها.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الـ heap complete tree متخزّنة في array، كل أب فيها أصغر من أولاده. بتضيف في الآخر وتطلّع لفوق، وبتشيل الـ root وتحط الأخير مكانه وتنزّله، والاتنين O(log n). وفي مسائل "أحسن k"، اللي فوق الـ heap هو اللي بيتطرد، فنوعها عكس اللي بتحتفظ بيه.
السؤالالإجابة
push / pop / peek؟O(log n) / O(log n) / O(1). والـ heapify O(n).
بنبدّل مع مين في الـ sift-down؟مع الابن الأصغر (أو الأحسن حسب الـ comparator).
max-heap في JS؟نفس الـ class بـ (a, b) => b - a.
أكبر k ولا أصغر k؟أكبر k: min-heap. أصغر k (أقرب k): max-heap.
محتاج أدوّر على عنصر معيّن؟الـ heap مش هتنفعك (O(n)). ده شغل BST أو Map.
الشرط اللي بيتنسى؟if (d.length > 0) في الـ pop، و i > 0 في الـ sift-up.

الفصل الجاي: كده خلّصنا الـ trees. في Graphs هتشوف tree من غير قواعد: أي node ممكن تتوصل بأي node، وممكن يبقى فيه دواير. هتبدأ بـ BFS و DFS، وبعدين في Dijkstra هتلاقي الـ heap دي راجعة: بدل الـ queue العادية، heap بتطلّع "أقرب node لحد دلوقتي" كل مرة.