ملخص Heap للمقابلات البرمجية
مقدمة
الـHeap هي بنية بيانات متخصصة قائمة على الـTrees، وهي Tree كاملة تحقق خاصية الـHeap.
- الـMax Heap — في الـMax Heap، يجب أن تكون قيمة العقدة هي الأكبر بين قيم العقد في شجرتها الفرعية بأكملها. ويجب أن تتحقق هذه الخاصية ذاتها بشكل تعاودي في جميع عقد الـTree.
- الـMin Heap — في الـMin Heap، يجب أن تكون قيمة العقدة هي الأصغر بين قيم العقد في شجرتها الفرعية بأكملها. ويجب أن تتحقق هذه الخاصية ذاتها بشكل تعاودي في جميع عقد الـTree.
في سياق مقابلات الـAlgorithms، يمكن التعامل مع الـHeaps وPriority Queues بوصفها Data Structure نفسها. والـHeap بنية بيانات مفيدة عندما يكون من الضروري إزالة العنصر ذي الأولوية الأعلى (أو الأدنى) بشكل متكرر، أو عندما تحتاج الإدراجات إلى التعاقب مع إزالات العقدة الجذر.
مصادر التعلم
- Learning to Love Heaps، basecs
- Heapify All The Things With Heap Sort، basecs
- Heaps، James Aspnes، جامعة Yale
التطبيقات الجاهزة
| اللغة | API |
|---|---|
| C++ | std::priority_queue |
| Java | java.util.PriorityQueue |
| Python | heapq |
| JavaScript | N/A |
الـtime complexity
| العملية | Big-O |
|---|---|
| إيجاد القيمة العظمى/الصغرى | O(1) |
| الإدراج | O(log(n)) |
| الحذف | O(log(n)) |
| الكمّ (إنشاء Heap من Array عناصر معطاة) | O(n) |
تقنيات
ذِكر k
إذا لاحظت ذِكر أكبر أو أصغر k قيم في المسألة، فهذا عادةً مؤشر على أنه يمكن استخدام Heap لحلها، كما في Top K Frequent Elements.
إذا كنت تحتاج إلى أكبر k عناصر، فاستخدم Heap دنيا بحجم k. مرّ على كل عنصر وأدخله في الـHeap (في مكتبة heapq في Python، اعكس إشارة القيمة قبل إدخالها لإيجاد القيمة العظمى). وكلما تجاوز حجم الـHeap k، أزل العنصر الأصغر؛ وهذا يضمن أن يبقى لديك أكبر k عناصر.
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.