دليل للأكوام في بايثون

المُقدّمة

تخيل مطارًا مزدحمًا تقلع فيه الرحلات الجوية وتهبط كل دقيقة. وكما يقوم مراقبو الحركة الجوية بتحديد أولويات الرحلات الجوية على أساس الاستعجال، فإن الأكوام تساعدنا على إدارة البيانات ومعالجتها بناءً على معايير محددة، مما يضمن إمكانية الوصول دائمًا إلى الجزء الأكثر "إلحاحًا" أو "أهمية" من البيانات في الأعلى.

في هذا الدليل، سنبدأ رحلة لفهم الأكوام من الألف إلى الياء. سنبدأ بإزالة الغموض عن ماهية الأكوام وخصائصها المتأصلة. من هناك، سوف نتعمق في تطبيق بايثون الخاص للأكوام، heapq الوحدة، واستكشف مجموعتها الغنية من الوظائف. لذا، إذا كنت قد تساءلت يومًا عن كيفية إدارة مجموعة ديناميكية من البيانات بكفاءة حيث تكون هناك حاجة بشكل متكرر إلى عنصر الأولوية الأعلى (أو الأدنى)، فأنت في مكان رائع.

ما هي الكومة؟

أول شيء تريد فهمه قبل الغوص في استخدام الأكوام هو ما هي الكومة. تبرز الكومة في عالم هياكل البيانات باعتبارها قوة قائمة على الأشجار، ولا سيما ماهرة في ذلك الحفاظ على النظام والتسلسل الهرمي. في حين أنها قد تشبه شجرة ثنائية للعين غير المدربة، إلا أن الفروق الدقيقة في بنيتها والقواعد الحاكمة تميزها بشكل واضح.

إحدى الخصائص المميزة للكومة هي طبيعتها ك شجرة ثنائية كاملة. وهذا يعني أن كل مستوى من الشجرة، باستثناء المستوى الأخير، ممتلئ بالكامل. ضمن هذا المستوى الأخير، يتم ملء العقد من اليسار إلى اليمين. يضمن مثل هذا الهيكل إمكانية تمثيل الأكوام ومعالجتها بكفاءة باستخدام المصفوفات أو القوائم، حيث يعكس موضع كل عنصر في المصفوفة موضعه في الشجرة.

ومع ذلك، فإن الجوهر الحقيقي للكومة يكمن في تنظيم. في كومة ماكس، فإن قيمة أي عقدة معينة تتجاوز أو تساوي قيم أطفالها، مع وضع العنصر الأكبر مباشرة في الجذر. ومن ناحية أخرى قال أ دقيقة كومة تعمل على المبدأ المعاكس: قيمة أي عقدة تكون إما أقل من أو تساوي قيم أبنائها، مما يضمن أن أصغر عنصر يقع في الجذر.

مع تقدمنا، سوف نتعمق أكثر في كيفية تمكين هذه الخصائص المتأصلة للأكوام من العمليات الفعالة وكيف تعمل بايثون heapq تدمج الوحدة الأكوام بسلاسة في مساعينا البرمجية.

خصائص وخصائص أكوام

تقدم الأكوام، ببنيتها الفريدة ومبادئ الترتيب، مجموعة من الخصائص والخصائص المميزة التي تجعلها لا تقدر بثمن في السيناريوهات الحسابية المختلفة.

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

خاصية أخرى ملحوظة للأكوام هي كفاءة الذاكرة. نظرًا لأنه يمكن تمثيل الأكوام باستخدام المصفوفات أو القوائم دون الحاجة إلى مؤشرات واضحة للعقد التابعة أو الأصل، فهي موفرة للمساحة. يتوافق موضع كل عنصر في المصفوفة مع موضعه في الشجرة، مما يتيح إمكانية الاجتياز والمعالجة بشكل مباشر ويمكن التنبؤ به.

خاصية ترتيب الأكوام، سواء كانت كومة كحد أقصى أو كومة دقيقة، تضمن ذلك يحمل الجذر دائمًا العنصر ذو الأولوية القصوى. هذا الترتيب المتسق هو ما يسمح بالوصول السريع إلى العنصر ذي الأولوية العليا دون الحاجة إلى البحث في البنية بأكملها.

علاوة على ذلك، هناك أكوام متعدد الجوانب. في حين أن الأكوام الثنائية (حيث يكون لكل والد طفلين على الأكثر) هي الأكثر شيوعًا، إلا أنه يمكن تعميم الأكوام على أكثر من طفلين، والمعروفة باسم د-اري أكوام. تسمح هذه المرونة بالضبط الدقيق بناءً على حالات الاستخدام المحددة ومتطلبات الأداء.

وأخيرا، أكوام ضبط النفس. كلما تمت إضافة عناصر أو إزالتها، يعيد الهيكل ترتيب نفسه للحفاظ على خصائصه. يضمن هذا التوازن الديناميكي بقاء الكومة مُحسّنة لعملياتها الأساسية في جميع الأوقات.

عندما نتعمق أكثر في تنفيذ لغة بايثون وتطبيقاتها العملية، سوف تتكشف أمامنا الإمكانات الحقيقية للأكوام.

أنواع الأكوام

لا يتم إنشاء كافة الأكوام على قدم المساواة. اعتمادًا على ترتيبها وخصائصها الهيكلية، يمكن تصنيف الأكوام إلى أنواع مختلفة، ولكل منها مجموعة تطبيقات ومزايا خاصة به. الفئتان الرئيسيتان هما كومة ماكس و دقيقة كومة.

الميزة الأكثر تميزا في أ كومة ماكس هو أن قيمة أي عقدة معينة أكبر من أو تساوي قيم أطفالها. وهذا يضمن أن العنصر الأكبر في الكومة يتواجد دائمًا في الجذر. مثل هذه البنية مفيدة بشكل خاص عندما تكون هناك حاجة للوصول بشكل متكرر إلى الحد الأقصى للعنصر، كما هو الحال في بعض تطبيقات قائمة الانتظار ذات الأولوية.

النظير إلى الحد الأقصى للكومة، أ دقيقة كومة يضمن أن قيمة أي عقدة معينة أقل من أو تساوي قيم أطفالها. يؤدي هذا إلى وضع أصغر عنصر في الكومة عند الجذر. تعد الحد الأدنى من الأكوام لا تقدر بثمن في السيناريوهات التي يكون فيها العنصر الأقل ذا أهمية قصوى، كما هو الحال في الخوارزميات التي تتعامل مع معالجة البيانات في الوقت الفعلي.

بالإضافة إلى هذه الفئات الأساسية، يمكن أيضًا تمييز الأكوام بناءً على عامل التفرع الخاص بها:

في حين أن الأكوام الثنائية هي الأكثر شيوعًا، حيث يكون لكل والد طفلين على الأكثر، يمكن توسيع مفهوم الأكوام ليشمل العقد التي لديها أكثر من طفلين. في د-اري كومة، كل عقدة لديها على الأكثر d أطفال. يمكن تحسين هذا الاختلاف لسيناريوهات محددة، مثل تقليل ارتفاع الشجرة لتسريع عمليات معينة.

كومة ذات الحدين عبارة عن مجموعة من الأشجار ذات الحدين التي يتم تعريفها بشكل متكرر. يتم استخدام الأكوام ذات الحدين في تطبيقات قائمة الانتظار ذات الأولوية وتوفر عمليات دمج فعالة.

سميت على اسم تسلسل فيبوناتشي الشهير كومة فيبوناتشي يوفر أوقات تشغيل مستهلكة بشكل أفضل للعديد من العمليات مقارنة بالأكوام الثنائية أو ذات الحدين. إنها مفيدة بشكل خاص في خوارزميات تحسين الشبكة.

تنفيذ كومة بايثون – com.heapq وحدة

تقدم بايثون وحدة مدمجة لعمليات الكومة - heapq وحدة. توفر هذه الوحدة مجموعة من الوظائف المتعلقة بالكومة والتي تسمح للمطورين بتحويل القوائم إلى أكوام وتنفيذ عمليات الكومة المختلفة دون الحاجة إلى تنفيذ مخصص. دعنا نتعمق في الفروق الدقيقة في هذه الوحدة وكيف توفر لك قوة الأكوام.

• heapq لا توفر الوحدة النمطية نوعًا مميزًا من بيانات الكومة. وبدلاً من ذلك، فهو يوفر وظائف تعمل على قوائم Python العادية، حيث يقوم بتحويلها ومعاملتها على أنها أكوام ثنائية.

يتميز هذا الأسلوب بالكفاءة في استخدام الذاكرة ويتكامل بسلاسة مع هياكل البيانات الموجودة في Python.

هذا يعني أن يتم تمثيل أكوام كقوائم in heapq. يكمن جمال هذا التمثيل في بساطته - حيث يعمل نظام فهرس القائمة الصفري كشجرة ثنائية ضمنية. لأي عنصر معين في الموضع i، إنه:

• الطفل الأيسر في موضعه 2*i + 1
• الطفل المناسب في الموقف 2*i + 2
• العقدة الأم في موضعها (i-1)//2

يضمن هذا الهيكل الضمني عدم الحاجة إلى تمثيل شجرة ثنائية منفصلة قائمة على العقد، مما يجعل العمليات مباشرة ويقلل استخدام الذاكرة إلى الحد الأدنى.

ومن الضروري أن نلاحظ أن heapq وحدة ينشئ أكوام دقيقة بشكل افتراضي. وهذا يعني أن أصغر عنصر يكون دائمًا في الجذر (أو في الموضع الأول في القائمة). إذا كنت بحاجة إلى الحد الأقصى للكومة، فسيتعين عليك عكس الترتيب عن طريق ضرب العناصر في -1 أو استخدم وظيفة المقارنة المخصصة.

بيثون heapq توفر الوحدة مجموعة من الوظائف التي تسمح للمطورين بتنفيذ عمليات الكومة المختلفة على القوائم.

في الأقسام التالية، سنتعمق في كل من هذه العمليات الأساسية، ونستكشف آلياتها وحالات استخدامها.

كيفية تحويل القائمة إلى كومة

• heapify() تعتبر الوظيفة نقطة البداية للعديد من المهام المتعلقة بالكومة. يستغرق الأمر تكرارًا (عادةً قائمة) ويعيد ترتيب عناصره في مكانه لتلبية خصائص الكومة الصغيرة:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

سيؤدي هذا إلى إخراج قائمة مُعاد ترتيبها تمثل الحد الأدنى من الكومة الصالحة:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

كيفية إضافة عنصر إلى الكومة

• heappush() تتيح لك الوظيفة إدراج عنصر جديد في الكومة مع الحفاظ على خصائص الكومة:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

سيعطيك تشغيل الكود قائمة بالعناصر التي تحافظ على خاصية الكومة الصغيرة:

[3, 5, 7]

كيفية إزالة وإرجاع أصغر عنصر من الكومة

• heappop() تقوم الدالة باستخراج وإرجاع أصغر عنصر من الكومة (الجذر في الكومة الدقيقة). بعد الإزالة، يضمن أن تظل القائمة كومة صالحة:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

سيؤدي هذا إلى إخراج أصغر عنصر والقائمة المتبقية:

1
[3, 7, 5, 9]

هنا، 1 هو أصغر عنصر من heap، وحافظت القائمة المتبقية على خاصية الكومة، حتى بعد أن قمنا بإزالتها 1.

كيفية دفع عنصر جديد وإخراج أصغر عنصر

• heappushpop() الدالة هي عملية مدمجة تدفع عنصرًا جديدًا إلى الكومة ثم تنبثق وتعيد أصغر عنصر من الكومة:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

هذا سوف يخرج 3، أصغر عنصر، وطباعة الجديد heap القائمة التي تتضمن الآن 4 مع الحفاظ على خاصية الكومة:

3
[4, 5, 7, 9]

كيفية استبدال أصغر عنصر ودفع عنصر جديد

• heapreplace() تقوم الدالة بإبراز أصغر عنصر وتدفع عنصرًا جديدًا إلى الكومة، كل ذلك في عملية واحدة فعالة:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

هذا يطبع 1، وهو أصغر عنصر، وتضم القائمة الآن 4 وتحافظ على خاصية الكومة:

1
[4, 5, 7, 9]

العثور على نهايات متعددة في كومة بايثون

nlargest(n, iterable[, key]) و nsmallest(n, iterable[, key]) تم تصميم الوظائف لاسترداد عناصر متعددة أكبر أو أصغر من عنصر قابل للتكرار. يمكن أن تكون أكثر كفاءة من فرز العناصر القابلة للتكرار بالكامل عندما تحتاج فقط إلى عدد قليل من القيم المتطرفة. على سبيل المثال، لنفترض أن لديك القائمة التالية وتريد البحث عن ثلاث قيم أصغر وثلاث أكبر قيم في القائمة:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

هنا، nlargest() و nsmallest() يمكن أن تكون الوظائف مفيدة:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

سيعطيك هذا قائمتين - تحتوي إحداهما على أكبر ثلاث قيم والأخرى تحتوي على أصغر ثلاث قيم من data قائمة:

[9, 6, 5]
[1, 1, 2]

كيفية بناء الكومة المخصصة الخاصة بك

بينما بايثون heapq توفر الوحدة النمطية مجموعة قوية من الأدوات للعمل مع الكومة، وهناك سيناريوهات حيث قد لا يكون سلوك الكومة الأدنى الافتراضي كافيًا. سواء كنت تتطلع إلى تنفيذ الحد الأقصى للكومة أو تحتاج إلى كومة تعمل بناءً على وظائف المقارنة المخصصة، فإن بناء كومة الذاكرة المؤقتة المخصصة يمكن أن يكون الحل. دعنا نستكشف كيفية تخصيص الأكوام لتناسب الاحتياجات المحددة.

تنفيذ ماكس كومة باستخدام heapq

افتراضيا، heapq يخلق أكوام دقيقة. ومع ذلك، مع خدعة بسيطة، يمكنك استخدامها لتنفيذ الحد الأقصى للكومة. والفكرة هي عكس ترتيب العناصر عن طريق ضربها -1 قبل إضافتها إلى الكومة:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

مع هذا النهج، يصبح العدد الأكبر (من حيث القيمة المطلقة) هو الأصغر، مما يسمح بذلك heapq وظائف للحفاظ على هيكل الكومة القصوى.

أكوام مع وظائف المقارنة المخصصة

في بعض الأحيان، قد تحتاج إلى كومة لا تتم مقارنتها فقط بناءً على الترتيب الطبيعي للعناصر. على سبيل المثال، إذا كنت تعمل مع كائنات معقدة أو لديك معايير فرز محددة، تصبح وظيفة المقارنة المخصصة ضرورية.

لتحقيق ذلك، يمكنك لف العناصر في فئة مساعدة تتجاوز عوامل المقارنة:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

باستخدام هذا الإعداد، يمكنك تحديد أي دالة مقارنة مخصصة واستخدامها مع الكومة.

وفي الختام

توفر الأكوام أداءً يمكن التنبؤ به للعديد من العمليات، مما يجعلها خيارًا موثوقًا للمهام القائمة على الأولوية. ومع ذلك، من الضروري مراعاة المتطلبات والخصائص المحددة للتطبيق المطروح. في بعض الحالات، قد يؤدي التغيير والتبديل في تنفيذ الكومة أو حتى اختيار هياكل بيانات بديلة إلى أداء أفضل في العالم الحقيقي.

إن الأكوام، كما مررنا عبرها، هي أكثر من مجرد بنية بيانات أخرى. إنها تمثل التقاء الكفاءة والهيكل والقدرة على التكيف. من خصائصها الأساسية إلى تنفيذها في بايثون heapq الوحدة النمطية، توفر الأكوام حلاً قويًا لعدد لا يحصى من التحديات الحسابية، خاصة تلك التي تتمحور حول الأولوية.

• محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
• PlatoData.Network Vertical Generative Ai. تمكين نفسك. الوصول هنا.
• أفلاطونايستريم. ذكاء Web3. تضخيم المعرفة. الوصول هنا.
• أفلاطون كربون، كلينتك ، الطاقة، بيئة، شمسي، إدارة المخلفات. الوصول هنا.
• أفلاطون هيلث. التكنولوجيا الحيوية وذكاء التجارب السريرية. الوصول هنا.
• المصدر https://stackabuse.com/guide-to-heaps-in-python/