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 بكتير، وده بالظبط سر سرعتها.
هتطلع من الفصل ده وإنت عارف
- إزاي 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 array | O(n) | O(1) | O(1) | كل إضافة بتزق عناصر |
تعمل sort كل مرة | O(1) | O(n log n) | O(n log n) | أسوأ حاجة فيهم |
| BST | O(h) | O(h) | O(h) | ممكن تميل فتبقى O(n) |
| Heap | O(log n) | O(1) | O(log n) | مضمونة دايمًا، بس مش بتدوّر على أي عنصر |
الـ heap هي الأداة اللي معمولة للسؤال ده بالظبط. والـ priority queue هو الاسم بتاع الفكرة: queue بتطلّع الأهم الأول مش اللي جه الأول. والـ heap هي الطريقة المشهورة اللي بنعمل بيها الـ priority queue. في الكلام هتسمع الاسمين كأنهم حاجة واحدة.
بص على heap صغيرة. هنضيف 6 أرقام، وبعدين نشيل أصغر واحد 3 مرات. الـ heap بتتعرض مرتين: tree فوق، ونفس الحاجة كـ array تحت:
لاحظ إن الـ array مش مترتبة، ومع كده أصغر رقم دايمًا في الخانة 0. ولاحظ إن كل pop طلّع الأصغر اللي فاضل، فالأرقام بتطلع مترتبة. ده اسمه heap sort لو عملته على كله.
طب إزاي تعرف من كلام المسألة إنها محتاجة heap؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
لو محتاج الأصغر مرة واحدة، loop عادية بـ Math.min O(n) وخلاص. لو كل الداتا قدامك ومحتاجها كلها مترتبة، sort مرة واحدة أسهل. الـ heap بتكسب لما الإضافة والشيل متداخلين، أو لما محتاج أحسن k بس من كتير. والـ sliding window maximum ليها أداة أحسن، الـ deque، في فصل الـ queue.
| الشكل | الفكرة | الـ complexity | مسائل |
|---|---|---|---|
| Top k | heap حجمها k، اللي فوق هو "البوّاب" اللي بيتشال أول واحد | O(n log k) | Kth Largest، K Closest، Top K Frequent |
| Simulation | كل خطوة خد الأهم، واعمل حاجة، ورجّع الناتج | O(n log n) | Last Stone Weight، Task Scheduler |
| K-way merge | heap فيها أول عنصر من كل list | O(N log k) | Merge k Sorted Lists، Kth in Sorted Matrix |
| Two heaps | max-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 فيها شرطين:
- الشكل (complete): كل المستويات مليانة على الآخر، ما عدا آخر مستوى ممكن يكون ناقص، بس بيتملي من الشمال لليمين من غير فراغات. يعني الـ tree دايمًا متوازنة: لو فيها n عنصر، الـ height حوالي
log₂ n. - الترتيب (heap property): كل أب أصغر من أو يساوي أولاده. وبس. مفيش أي شرط بين الأخين، ولا بين الشمال واليمين.
من الشرط التاني: الأب أصغر من أولاده، وأولاده أصغر من أولادهم، وهكذا. يبقى الـ root أصغر من الكل. وده كل اللي محتاجينه.
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.
x >> 1بيزق الـ bits خانة لليمين، يعني قسمة على 2 وترمي الكسر (التفاصيل في فصل الـ bits). من غير floor،i = 4هتدّيك 1.5، وh[1.5]بـundefinedمن غير أي error.- الأولاد. ممكن يطلعوا برا الـ array: لو
2 * i + 1 >= h.lengthيبقى الـ node دي leaf. أي كود بيستخدمleft(i)لازم يشيّك ده الأول. - نبدأ من 1 لأن الـ root (index 0) مالوش أب. لو بدأت من 0،
parent(0)هتطلع-1، وh[-1]بـundefined. - بنشيّك كل node مع أبوها. كل علاقة أب وابن بتتشيّك مرة واحدة بالظبط، فالـ check ده O(n). لو كله تمام، يبقى min-heap.
شوف نفس الـ heap كـ tree وكـ array. الرقم بين القوسين تحت كل node هو الـ index بتاعها في الـ array:
طب لو ضفنا رقم جديد، إزاي القاعدة تفضل ماشية؟
الـ push: حطه في الآخر، وطلّعه لفوق (sift-up)
عايزين نضيف رقم. عندنا شرطين لازم يفضلوا صح: الشكل والترتيب.
- الشكل: المكان الوحيد اللي يخلّي الـ tree لسه complete هو أول خانة فاضية في آخر مستوى، وده آخر الـ array. فبنعمل
h.push(x)عادي. - الترتيب: كل حاجة كانت heap قبل كده، فالمكان الوحيد اللي ممكن يبقى فيه مشكلة هو بين الرقم الجديد وأبوه. لو الجديد أصغر من أبوه، نبدّلهم. دلوقتي ممكن يبقى أصغر من جدّه، فنكرر. ونقف لما أبوه يبقى أصغر منه أو يساويه، أو لما يوصل للـ root.
- ليه التبديل مش بيبوّظ حاجة تحت؟ الأب اللي نزل كان أصغر من أو بيساوي كل اللي تحته (ده كان heap)، والمكان اللي نزل فيه جوه نفس الـ subtree، فهو لسه أصغر من كل اللي تحته. والجديد اللي طلع أصغر من الأب، والأب كان أصغر من أخوه التاني، فالجديد أصغر من الأخ برضه.
- الرقم بيدخل في آخر الـ array، يعني آخر مكان في آخر مستوى. الشكل اتحل في سطر واحد.
iهو مكان الرقم الجديد دلوقتي، وهيتحرك معاه.h.length - 1لأن الـ push زوّد الطول خلاص، والـ index الأخير هو الطول ناقص 1.- ليه
i > 0مشi >= 0؟ لماi = 0يبقى وصلنا للـ root، ومالوش أب نقارن بيه. لو كتبت>= 0، هتحسبp = -1وتقارن بـh[-1]. - أب الـ
i، بنفس المعادلة اللي فوق. - ليه
<=؟ لو الأب بيساوي الجديد، القاعدة متحققة ومفيش داعي نبدّل. والـbreakده early exit: اللي فوق كان heap أصلًا، فمش محتاجين نكمّل. - التبديل بالـ destructuring: الطرف اليمين بيتحسب الأول كـ array مؤقتة، وبعدين بيتوزع. بديل للـ
tempالتقليدي. - الرقم بقى في مكان أبوه، فنكمّل من هناك. كل لفة بتطلع مستوى، والـ height حوالي
log n، فالـ push كلهO(log n).
هنضيف 1 (هيطلع لحد الـ root)، وبعدين 7 (هيطلع خطوة ويقف):
الإضافة طلّعت الرقم لفوق. الشيل بيعمل العكس: بينزّل رقم لتحت.
الـ pop: خد الـ root، وحط الأخير مكانه ونزّله (sift-down)
أصغر رقم في الـ root، فده اللي هنرجّعه. بس لو شلناه، هيبقى فيه فتحة فوق. الحل:
- الشكل: العنصر الوحيد اللي نقدر نشيله والـ tree تفضل complete هو آخر عنصر في الـ array. فنشيله بـ
h.pop()، ونحطه مكان الـ root. - الترتيب: الرقم ده جاي من تحت خالص، فغالبًا كبير. نقارنه بأولاده: لو أكبر من أي واحد فيهم، نبدّله مع الأصغر فيهم، ونكرر لحد ما يبقى أصغر من الاتنين أو يوصل leaf.
- ليه مع الأصغر بالذات؟ اللي هيطلع فوق هيبقى أب للابن التاني. لو طلّعنا الأكبر، هيبقى أب لابن أصغر منه، والقاعدة اتكسرت. الأصغر هو الوحيد اللي ينفع يبقى أب للاتنين.
- heap فاضية، مفيش حاجة نرجّعها. بنرجّع
undefinedزي[].pop(). - بنحفظ الإجابة قبل ما نلمس أي حاجة، لأن الـ
h[0]هيتكتب عليه بعد سطرين. - بنشيل آخر عنصر. ده O(1)، بعكس
h.shift()اللي بتشيل الأول وتزق كل الباقي O(n). - أهم شرط في الدالة. لو الـ heap كان فيها عنصر واحد، الـ
h.pop()شاله وبقت فاضية. لو كتبناh[0] = lastمن غير الشرط ده، هنرجّع العنصر تاني، والـ heap عمرها ما هتفضى. - الأخير بقى في الـ root، و
iماشي معاه. - أولاد
i. ممكن يكونوا برا الـ array، وده بنشيّكه في السطرين الجايين. smallهو "أصغر واحد من التلاتة":iوأولاده. بنبدأ بافتراض إنiنفسه هو الأصغر.- ليه
l < h.lengthالأول؟ لو الابن مش موجود، الـ&&بتقف قبل ما تقراh[l]. وخلي بالك: السطر 12 بيقارن بـh[small]مشh[i]، عشان نختار الأصغر من الابنين، مش أول واحد أصغر من الأب. - لو
iنفسه أصغر من أولاده (أو مالوش أولاد)، يبقى وصل لمكانه. - نبدّله مع الابن الأصغر وننزل معاه. كل لفة بتنزل مستوى، فالـ pop كله
O(log n). - بنرجّع الأصغر اللي حفظناه في السطر 3.
هنعمل pop مرتين من الـ heap اللي طلعت من الـ push فوق:
الدالتين دول شغالين على أرقام بس. المسائل الحقيقية فيها أزواج ونقط و nodes، وساعات max-heap.
الـ class: MinHeap بـ comparator
الدالتين اللي فوق شغالين على أرقام بس، ومع <. في المسائل الحقيقية هتحط في الـ heap أزواج [value, freq]، أو نقط [x, y]، أو list nodes، وساعات هتحتاج max-heap. الحل: comparator، بنفس فكرة الـ comparator بتاع sort اللي في فصل الـ sorting.
compare(a, b) بيرجّع رقم. سالب يعني a لازم يبقى فوق b. موجب يعني b فوق. صفر يعني مش فارقة. الـ default (a, b) => a - b بيدّي min-heap. والـ (a, b) => b - a بيقلبها max-heap من غير ما تغيّر سطر في الـ class.
- الاسم
MinHeapمعناه: اللي الـ comparator بيقول عليه "أصغر" بيطلع فوق. لو بعتّله comparator مقلوب، هيشتغل max-heap. ممكن تسميهاHeapبس، بسMinHeapبتفكّرك بالـ default. - default parameter: لو ما بعتّش comparator، يبقى أرقام عادية والأصغر فوق. لازم يرجّع رقم مش boolean.
(a, b) => a < bبترجّعtrueأوfalse، والـ class بتقارن النتيجة بـ< 0، والـ boolean عمره ما هيبقى أقل من صفر، فالـ heap مش هتترتب خالص. - الـ array اللي فيها الـ tree، والـ comparator. الاتنين على
thisعشان كل الـ methods تشوفهم. sizeوpeekالاتنين O(1). الـpeekبيرجّع الأهم من غير ما يشيله.- نفس الـ push اللي فوق: في الآخر، وبعدين sift-up من آخر index.
- نفس الـ pop اللي فوق بالظبط، والـ sift-down اتنقل لـ method لوحده. السطر 17 هو نفس الشرط المهم بتاع "العنصر الوحيد".
- بدل
h[p] <= h[i]بقتcompare(d[i], d[p]) >= 0، ومعناها: الابن مش لازم يبقى فوق أبوه. خلي بالك من ترتيب الـ arguments: الابن الأول والأب التاني، يعني "هل الابن ينفع يبقى فوق الأب؟". - نفس الـ sift-down، والمقارنة بقت
compare(d[l], d[best]) < 0: "الابن ده لازم يبقى فوق أحسن واحد لحد دلوقتي؟". سمّيناهbestبدلsmallلأنه في max-heap هيبقى الأكبر.
لو عندك الأرقام كلها من الأول، فيه طريقة أسرع من إنك تعمل push لكل واحد.
Heapify: تحوّل array كاملة لـ heap في O(n)
لو عندك n رقم من الأول، ممكن تعمل push لكل واحد: n مرة × O(log n) = O(n log n). بس فيه طريقة أسرع: سيب الأرقام في مكانها، وصلّح الـ tree من تحت لفوق.
- الـ leaves heaps جاهزة: node لوحدها مفيهاش أي أب وابن يتخانقوا. ونص الـ array تقريبًا leaves: كل index من
n >> 1لآخر الـ array ملوش أولاد، لأن2i + 1 >= n. - نمشي بالعكس: من آخر أب (
(n >> 1) - 1) لحد الـ root، ونعمل sift-down لكل واحد. ليه بالعكس؟ لأن الـ sift-down محتاج إن أولاد الـ node يكونوا heaps، ولما بنمشي من تحت، بنكون صلّحنا الأولاد قبل الأب. - ليه 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 | الشغل |
|---|---|---|---|
| الـ leaves | n / 2 | 0 | 0 |
| فوقهم | n / 4 | 1 | n / 4 |
| فوقهم | n / 8 | 2 | n / 4 |
| فوقهم | n / 16 | 3 | 3n / 16 |
| ... | ... | ... | المجموع أقل من n |
(h.length >> 1) - 1هو آخر index ليه ابن: معn = 7ده 2، وأولاده 5 و 6. وi >= 0بالـ=عشان الـ root لازم يتصلّح هو كمان.- لحظة ما نوصل لـ
i، كل الـ indices الأكبر منه اتصلّحت، يعني أولاده heaps. فالـ sift-down هنا صح. - نفس الـ 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 |
|---|---|---|
| Python | heapq | min-heap على list عادية |
| Java | PriorityQueue | min-heap |
| C++ | std::priority_queue | max-heap. للـ min استخدم greater<int> |
| JavaScript | مفيش | اكتبها بإيدك |
LeetCode بيحط مكتبة اسمها @datastructures-js/priority-queue في بيئة الـ JS بتاعته (فيها MinPriorityQueue و MaxPriorityQueue)، بس الـ API بتاعها اتغيّر بين النسخ، وفي انترفيو حقيقي أو موقع تاني مش هتلاقيها. فالأضمن إنك تعرف تكتب الـ class بنفسك.
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
رجّع العنصر رقم k من ناحية الكبير. يعني لو رتّبت الـ array تنازلي، العنصر اللي في المكان رقم k (والمتكرر بيتحسب كل مرة).
نفكّر فيها مع بعض
- أول حل: رتّب تنازلي ورجّع
nums[k - 1]. ده O(n log n)، وصح، وفي الانترفيو قوله الأول. بس الـ interviewer هيسأل "تقدر أحسن؟" أو "لو الأرقام جاية stream مش عارف آخرها؟". - محتاجين إيه بالظبط؟ مش محتاجين الترتيب كله. محتاجين نعرف أكبر k رقم، وأضعف واحد فيهم هو الإجابة.
- الـ key insight: نعمل "نادي" فيه k كراسي بس، فيه أكبر k رقم شفناهم لحد دلوقتي. أي رقم جديد بييجي، بنقارنه بـ أضعف عضو في النادي (الأصغر فيهم). لو الجديد أكبر، الأضعف يطلع والجديد يدخل.
- ليه min-heap مش max-heap؟ لأن اللي محتاجين نوصله بسرعة ونشيله هو الأصغر في النادي، مش الأكبر. الـ min-heap بتحط الأصغر فوق. وبعد ما نلف على كله، النادي فيه أكبر k، والـ
peekهو أصغرهم، يعني الـ kth largest بالظبط. - الحالات الطرفية:
k = 1(أكبر رقم)،k = n(أصغر رقم)، أرقام متكررة، أرقام سالبة.
- min-heap بالـ comparator الـ default. الـ heap دي عمرها ما هتعدّي
k + 1عنصر. - كل رقم بيدخل النادي الأول. حتى لو صغير، هيطلع في السطر الجاي.
- ليه
> kمش>= k؟ عايزين النادي فيه k بالظبط. مع>= kهتشيل وهم k فيبقواk - 1، وترجّع الإجابة الغلط. جرّبها في دماغك بـk = 1. - أصغر واحد في أكبر 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.
هنا كان الـ min-heap كفاية. طب لو محتاج الأكبر كل مرة، والناتج بيرجع يتنافس تاني؟
مثال محلول 2: Last Stone Weight
عندك حجارة بأوزان. كل دور خد أتقل حجرين وخبطهم ببعض: لو وزنهم واحد الاتنين بيختفوا، ولو مختلفين التقيل بيفضل منه الفرق. كمّل لحد ما يفضل حجر واحد أو مفيش. رجّع وزن الأخير، أو 0.
نفكّر فيها مع بعض
- الجديد هنا: max-heap بالـ comparator المقلوب، والناتج بيرجع الـ heap تاني. ده pattern اسمه simulation.
- Simulation: المسألة بتقولك تعمل إيه بالظبط، مفيش حيلة. السؤال بس: إزاي تجيب أتقل اتنين بسرعة كل دور؟
- Brute force: رتّب كل دور. n دور × O(n log n) = O(n² log n). مع 30 حجر (الـ constraint) هيعدّي، بس الـ heap هو المقصود.
- الفكرة: "أتقل حاجة" كل شوية، والفرق بيرجع يتحط تاني. ده max-heap: نفس الـ class بـ comparator مقلوب.
- الحالات الطرفية: حجر واحد من الأول (يرجع هو)، كل الحجارة بتختفي (يرجع 0).
b - a: لوbأكبر، الناتج موجب، يعنيbفوق. فالأكبر بيطلع فوق. ده الـ max-heap كله، من غير ما نكتب class تانية.- push لكل حجر، O(n log n). ممكن heapify في O(n) بس مش فارقة هنا.
- ليه
> 1؟ محتاجين حجرين عشان نخبطهم. لو فاضل واحد أو صفر نقف. لو كتبت> 0، أول ما يفضل حجر واحد هتعمل pop مرتين، والتانية هترجعundefined. - الأول اللي يطلع هو الأتقل، فـ
y >= xمضمونة، والفرقy - xعمره ما هيبقى سالب. - لو متساويين، الاتنين اختفوا ومفيش push. لو لأ، الباقي يرجع الـ heap ويتنافس من جديد.
- لو فاضل حجر، وزنه هو الإجابة. لو الـ heap فاضية، 0.
التعقيد: كل دور بيقلل عدد الحجارة واحد على الأقل، فعدد الأدوار أقل من n، وكل دور O(log n). المجموع O(n log n) والـ memory O(n).
طب لو عايز أصغر k مش أكبر k، والعناصر نقط مش أرقام؟
مثال محلول 3: K Closest Points to Origin
عندك نقط [x, y]. رجّع أقرب k نقط لنقطة الأصل (0, 0)، بأي ترتيب.
نفكّر فيها مع بعض
- الجديد هنا: نفس نادي 215، بس عايزين الأصغر k، والعناصر arrays مش أرقام.
- المسافة:
sqrt(x² + y²). بس إحنا بنقارن مسافات بس، والـ sqrt بتحافظ على الترتيب (لوa² < b²يبقىa < bللموجب). فنقارنx² + y²على طول، من غير sqrt، ومن غير كسور. - نفس فكرة النادي: عايزين أقرب k. النادي فيه k نقط، والبوّاب واقف جنب أضعف واحد، وهنا الأضعف هو الأبعد. فالـ heap لازم تطلّع الأبعد فوق: max-heap بالمسافة.
- القاعدة اللي تحفظها: نوع الـ heap عكس اللي بتحتفظ بيه. عايز أكبر k؟ min-heap. عايز أصغر k (أقرب k)؟ max-heap. لأن الـ heap فوقها اللي هيتطرد.
- الحالات الطرفية:
k = n(رجّع كله)، نقطتين بنفس المسافة (أي واحدة تنفع).
- المسافة المربعة. مع الـ constraints (إحداثيات لحد 10⁴) أكبر قيمة
2 × 10⁸، بعيد جدًا عن حدود الأرقام في JS. dist(b) - dist(a)مقلوبة، فالأبعد فوق. الـ heap فيها النقط نفسها (arrays)، والـ comparator هو اللي بيعرف يقارنها.- نفس سطرين الـ 215 بالظبط. الـ pop بيطرد الأبعد في النادي.
- المسألة بتقبل أي ترتيب، فبنرجّع الـ array الداخلية على طول. لو عايزهم مترتبين من الأقرب، اعمل pop لحد ما تفضى واقلب النتيجة.
تحت كل node النقطة نفسها، والرقم جوه الدايرة هو المسافة المربعة:
التعقيد: O(n log k) وقت و O(k) memory. والـ sort على المسافة O(n log n) حل مقبول برضه، قوله الأول.
لحد دلوقتي العناصر كانت جاهزة. طب لو لازم تحسبها الأول؟
مثال محلول 4: Top K Frequent Elements
رجّع الـ k أرقام اللي اتكرروا أكتر حاجة، بأي ترتيب. الإجابة مضمون إنها واحدة.
نفكّر فيها مع بعض
- الجديد هنا: العناصر مش جاهزة. بنبنيها الأول (Map للعدّ)، وبعدين نفس النادي على أزواج
[value, freq]. - خطوة 1: نعدّ.
Mapمن الرقم لعدد مراته، زي ما اتعلمت في فصل الـ hashing. O(n). - خطوة 2: أكبر k في العدد. دلوقتي عندنا أزواج
[value, freq]، وعايزين أكبر k بالـ freq. ده 215 تاني بالظبط، بس على الـ freq: نادي فيه k، والبوّاب واقف جنب الأقل تكرار، يعني min-heap بالـ freq. - ليه مش sort؟ الـ sort على كل الأزواج O(m log m) حيث m عدد الأرقام المختلفة. الـ heap O(m log k). الاتنين مقبولين، والـ heap أحسن لما k صغير.
- الحالات الطرفية:
kبيساوي عدد الأرقام المختلفة (رجّع كلهم)، رقم واحد بس متكرر.
- العدّ.
(count.get(x) || 0)عشان أول مرة الـgetبترجّعundefined، وundefined + 1بـNaN. - الـ comparator بيقارن بالعنصر التاني (
[1])، وده الـ freq.a[1] - b[1]مش مقلوبة، فالأقل تكرار فوق. - اللف على
Mapبـfor...ofبيدّيك[key, value]في كل لفة، بنفس ترتيب الإضافة. - نفس سطرين النادي.
- الـ 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
عندك k linked lists، كل واحدة مترتبة تصاعدي. ادمجهم في linked list واحدة مترتبة.
تذكير من فصل الـ linked list: كل node فيها val و next، والـ dummy node هي node وهمية بنحطها في الأول عشان ما نعملش حالة خاصة لأول عنصر، وفي الآخر بنرجّع dummy.next.
نفكّر فيها مع بعض
- الجديد هنا: الـ heap مش بتمسك "أحسن k"، بتمسك مرشح واحد من كل list، وكل ما واحد يطلع اللي وراه يدخل.
- Brute force: لم كل القيم في array، رتّب، وابني list جديدة. O(N log N) حيث N مجموع كل العناصر. شغال، بس مش مستغل إن كل list مترتبة.
- دمج واحدة واحدة: ادمج الأولى مع التانية، والنتيجة مع التالتة... كل دمج بيلف على كل اللي اتجمع لحد دلوقتي، فالمجموع حوالي O(N × k).
- الفكرة: العنصر الجاي في النتيجة أكيد واحد من رؤوس الـ lists (أول عنصر لسه ما اتاخدش في كل list)، لأن كل list مترتبة. يعني في كل لحظة عندنا k مرشحين بس. نحطهم في min-heap، ونطلّع الأصغر، ونحط مكانه اللي بعده في نفس الـ list.
- ليه ده صح؟ اللي بعده في نفس الـ list هو المرشح الجديد الوحيد. كل الـ lists التانية رؤوسها ما اتغيرتش.
- الحالات الطرفية:
lists = []، list فاضية جوه الـ lists (null)، list واحدة بس.
- الـ heap فيها nodes مش أرقام، والـ comparator بيقارن بالـ
val. ميزة إننا بنحط الـ node نفسها: بنعرف اللي بعدها منnode.nextمن غير ما نشيل رقم الـ list. - ليه
head !== null؟ الـ lists ممكن يكون فيها list فاضية. لو حطيتnullفي الـ heap، الـ comparator هيقراnull.valويضرب error. - الـ dummy والـ tail. الـ
tailدايمًا آخر node في النتيجة. - طول ما فيه مرشحين، الأصغر فيهم هو الجاي في الترتيب.
- نعلّقه في آخر النتيجة ونحرّك الـ tail. مش بنعمل nodes جديدة، بنعيد ربط الموجودين.
- اللي بعده في نفس الـ list ياخد مكانه كمرشح. لو الـ list خلصت، الـ heap بتصغر واحد.
- أول node حقيقية. ولو كل الـ lists فاضية،
dummy.nextبـnull، وده الصح.
التعقيد: كل عنصر من الـ N بيدخل الـ heap مرة ويطلع مرة، والـ heap عمرها ما بتعدّي k. يعني O(N log k) وقت و O(k) memory. لو k = 10⁴ و N = 10⁴، ده أسرع كتير من O(N × k).
آخر مثال: مش أكبر ولا أصغر، عايزين اللي في النص. heap واحدة مش كفاية.
مثال محلول 6: Find Median from Data Stream
اعمل class فيها addNum(num) بتضيف رقم، و findMedian() بترجّع الـ median لكل اللي اتضاف لحد دلوقتي. الـ median هو اللي في النص بعد الترتيب، ولو العدد زوجي يبقى متوسط اللي في النص.
نفكّر فيها مع بعض
- الجديد هنا: heap اتنين شغالين مع بعض، واحدة max وواحدة min.
- Brute force: array مترتبة، وكل إضافة تحطها في مكانها (binary search على المكان، وبعدين
splice). الـ splice بيزق العناصر، فكل إضافة O(n). - الـ median محتاج إيه؟ مش محتاج الترتيب كله. محتاج أكبر واحد في النص الصغير وأصغر واحد في النص الكبير. الاتنين دول اللي في النص.
- الفكرة: نقسم الأرقام نصين. النص الصغير في max-heap اسمها
low(فوقها أكبر الصغيرين). النص الكبير في min-heap اسمهاhigh(فوقها أصغر الكبار). ونحافظ على شرطين: كل اللي فيlowأصغر من أو يساوي كل اللي فيhigh، وlowيا قدhighيا أكبر منها بواحد. - الـ median: لو
lowأكبر بواحد، العدد فردي والـ median هوlow.peek(). لو متساويين، متوسط الـ peeks. - الحيلة في الإضافة: كل رقم جديد يدخل
lowالأول، وبعدين أكبر واحد فيlowينتقل لـhigh. ده بيضمن شرط الترتيب من غير ما نقارن بإيدنا. وبعدين لوhighبقت أكبر، نرجّع أصغر واحد فيها لـlow.
lowmax-heap، فالـpeekبتاعها هو أكبر رقم في النص الصغير. ده اللي جنب النص على طول من الشمال.highmin-heap، فالـpeekبتاعها أصغر رقم في النص الكبير، اللي جنب النص من اليمين.- ليه low الأول وبعدين high؟ اللي بيطلع من
lowهو أكبر واحد فيها، فلما يروحhighالـ invariant "كل low <= كل high" بيفضل صح، من غير ولاif. - لو
highبقت أكبر، نرجّع أصغرها لـlow. اخترنا إنlowهي اللي تاخد الزيادة، فالـ median في العدد الفردي يبقىlow.peek()دايمًا. - عدد فردي:
lowفيها واحد زيادة، وأكبرها هو اللي في النص بالظبط. - عدد زوجي: النص بين أكبر الصغيرين وأصغر الكبار. القسمة على 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 واحد بس).
تمرين: فكّر قبل ما تفتح
اعمل class بتاخد k و array أولية. بعد كده كل add(val) بتضيف رقم وترجّع الـ kth largest لحد دلوقتي.
تلميح 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 دقيقة، ارجع للمثال المحلول اللي شبهها.
- Last Stone Weightأول heap ليك: max-heap بالـ comparator المقلوب.
- Kth Largest Element in a Streamالنادي اللي حجمه k جوه class.
- Kth Largest Element in an Arrayالمثال المحلول 1. افهم ليه min-heap.
- K Closest Points to Originنفس النادي بالعكس: max-heap بالمسافة.
- Top K Frequent ElementsMap للعدّ وبعدين heap على الأزواج.
- Sort Characters By Frequencyنفس 347 بس بتطلّع الكل بالترتيب: pop لحد ما تفضى.
- Furthest Building You Can Reachheap للسلالم: لما تخلص، اللي فوق الـ heap يتحوّل طوب. heap مع greedy.
- Task Schedulersimulation: خد الأكتر تكرار كل دور. (وفيه حل رياضي أقصر.)
- Reorganize Stringخد أكتر حرفين تكرار كل دور، ورجّعهم بعد ما تنقّصهم.
- Kth Smallest Element in a Sorted Matrixk-way merge على الصفوف، وتقف عند رقم k.
- Merge k Sorted Listsالمثال المحلول 5: heap الرؤوس.
- Find Median from Data Streamالمثال المحلول 6: two heaps.
- IPOاختياري: 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 لحد دلوقتي" كل مرة.