فرز الهرم: مبدأ التشغيل والميزات

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

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

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

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

1. ما هو الهرم الفرز?
2. مبدأ فرز الهرم
3. مزايا فرز الهرم
4. تعقيد فرز الهرم
5. ملامح تنفيذ الفرز الهرمي
6. استخدام الفرز الهرمي
7. مثال على فرز الهرم
8. سؤال وجواب
9. كيف الهرم الفرز العمل?
10. ما هي ملامح الهرم الفرز?
11. كيف يمكنني إنشاء كومة ثنائية للفرز الهرمي?
12. لماذا الفرز الهرمي فعال?
13. هل من الممكن استخدام الفرز الهرمي لفرز هياكل البيانات الأخرى?
14. هل هناك عيوب لفرز الهرم?

ما هو الهرم الفرز?

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

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

تتضمن عملية فرز الهرم عدة خطوات:

1. بناء هرم من مجموعة بيانات معينة.
2. إزالة أكبر عنصر (الجزء العلوي من الهرم) واستبداله بالعنصر الأخير من الهرم.
3. كرر الخطوة 2 للهرم المتبقي.
4. استخراج العناصر من الهرم في ترتيب عكسي للحصول على مجموعة فرزها.

الفرز الهرمي له وقت تشغيل س (ن * سجل (ن)) ، أين ن هو عدد العناصر المراد فرزها. إنه نوع مستقر ، أي أنه لا يغير ترتيب العناصر المتساوية.

يجد الفرز الهرمي تطبيقه في العديد من المجالات التي تتطلب الفرز الفعال لكميات كبيرة من البيانات ، مثل قواعد البيانات وأنظمة المعلومات.

مبدأ فرز الهرم

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

عملية الفرز هي كما يلي:

1. تحتاج أولا إلى بناء هرم من المصفوفة الأصلية. للقيام بذلك ، نذهب من خلال جميع عناصر المصفوفة ولكل عنصر نسميه الإجراء "سيفتدون" ، الذي يعيد الشرط "الطفل أصغر من الوالد".
2. بعد بناء الهرم ، يكون العنصر الأكبر في الجذر. مبادلة جذر الهرم مع قيمة العنصر الأخير من مجموعة وتقليل حجم الهرم بنسبة 1.
3. كرر عملية الغربلة لجذر هرمي جديد. وبالتالي ، في كل تكرار ، يتم تحديد الحد الأقصى للعنصر ووضعه في مكانه.
4. تتكرر العملية حتى يصبح حجم الهرم مساويا لـ 1. نتيجة لذلك ، سيتم فرز المصفوفة الأصلية بترتيب تصاعدي.

ميزة الفرز الهرمي هي كفاءته وسهولة تنفيذه. الخوارزمية لها تعقيد زمني لـ ا (ن سجل ن) ، أين ن هو عدد العناصر في المصفوفة. أيضا ، الفرز الهرمي مستقر ، أي أنه لا يغير ترتيب العناصر المتساوية.

مزايا فرز الهرم

يعد الفرز الهرمي أحد أكثر خوارزميات الفرز كفاءة. يمكن وصف مزاياها على النحو التالي:

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

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

تعقيد فرز الهرم

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

لنفترض أن لدينا مجموعة من العناصر ن. يمكن تقدير وقت تنفيذ الفرز الهرمي كـ ا (نلوغن) ، أين ن هو عدد العناصر في المصفوفة. وبالتالي ، فإن الفرز الهرمي له تعقيد زمني لوغاريتمي.

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

القيمة س (نلوغن) يشير إلى أنه إذا تضاعف حجم الصفيف ، فإن وقت الفرز سيزيد مرتين تقريبا. على سبيل المثال ، إذا كانت المصفوفة تحتوي على 100 عنصر ، فسيكون وقت تنفيذ الفرز الهرمي حوالي 200 وحدة زمنية. إذا زادت المصفوفة إلى 200 عنصر ، فسيزيد وقت الفرز إلى 400 وحدة زمنية.

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

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

ملامح تنفيذ الفرز الهرمي

الفرز الهرمي هو طريقة فرز فعالة تعتمد على استخدام بنية بيانات تسمى الهرم. ومع ذلك ، قد يكون لتنفيذ الفرز الهرمي بعض الميزات الخاصة:

1. يمكن تنفيذ الهرم باستخدام مصفوفة أو قائمة مرتبطة. في حالة التنفيذ باستخدام مصفوفة ، يجب أن يؤخذ في الاعتبار أن فهارس المصفوفة تبدأ بـ 0 أو 1 ، اعتمادا على لغة البرمجة. قد يؤثر هذا على الصيغ لحساب العناصر الأم والطفل في الهرم.
2. لتنفيذ هرم باستخدام مصفوفة ، يجب عليك أولا تهيئة مصفوفة بالطول المطلوب. قد يستغرق هذا بعض الوقت ، خاصة إذا كانت المصفوفة كبيرة بما يكفي. من الضروري أخذ هذه الحقيقة في الاعتبار عند العمل مع الفرز الهرمي.
3. جانب مهم من تنفيذ الفرز الهرمي هو البناء الصحيح للهرم قبل البدء في الفرز. للقيام بذلك ، قم بإجراء عملية غربلة لأسفل (كومة) لكل عنصر ، بدءا من منتصف المصفوفة وحتى جذر الهرم. قد يتطلب ذلك موارد حوسبة كبيرة ، خاصة للمصفوفات الكبيرة.
4. عند إزالة أكبر عنصر من الهرم واستعادة خصائصه ، تحتاج إلى إجراء عملية فرز لنقل العنصر إلى الموقع المطلوب في الهرم. يمكن أن تكون هذه العملية مكلفة للغاية ، خاصة بالنسبة للهرم الذي يحتوي على العديد من العناصر.

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

استخدام الفرز الهرمي

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

مزايا استخدام الفرز الهرمي:

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

يمكن استخدام تنفيذ الفرز الهرمي في الحالات التالية:

1. فرز المصفوفات: يعد الفرز الهرمي أمرا رائعا لفرز المصفوفات بأي طول ، بما في ذلك كميات كبيرة من البيانات.
2. فرز هياكل البيانات: يمكن استخدام الفرز الهرمي لفرز هياكل البيانات المختلفة مثل القوائم أو الأشجار المرتبطة.
3. قائمة انتظار الأولوية: يتم استخدام الفرز الهرمي لتنفيذ قائمة انتظار الأولوية ، حيث يتم ترتيب العناصر حسب الأولوية ويمكن استرجاعها بترتيب الأولوية المحددة.

يمكن تطبيق الفكرة العامة للفرز الهرمي في العديد من الخوارزميات وهياكل البيانات لمعالجة وتنظيم كميات كبيرة من المعلومات بكفاءة.

مثال على فرز الهرم

لنلق نظرة على مثال للفرز الهرمي على مجموعة من الأرقام:

مجموعة المصدر:

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

الخطوة 1: بناء الهرم

7

/ \

2 3

/ \ / \

5 1 9 4

/ \

6 8

الخطوة 2: إعادة بناء الهرم

9

/ \

8 3

/ \ / \

7 1 2 4

/ \

6 5

الخطوة 3: إعادة بناء الهرم واستخراج العناصر القصوى

8 7 6 5 4 3 2 1

/ \ / \ / \ / \ / \ / \ / \ / \

7 3 -> 6 3 -> 5 3 -> 4 3 -> 3 3 -> 2 1 -> 2 1 -> 1 1

/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \

5 1 2 4 5 1 2 4 4 1 2 4 4 1 2 1 3 1 2 1 3 2 2 1 3 2 2 1 2 1 2 1

الخطوة 4: اكتمال الفرز

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

مجموعة المصدر[7, 2, 3, 5, 1, 9, 4, 6, 8] يتم فرزها باستخدام الفرز الهرمي. أولا ، يتم بناء الهرم ، ثم يتم إعادة بناء الهرم ويتم استخراج العناصر القصوى حتى يصبح الهرم فارغا. نتيجة لذلك ، نحصل على مصفوفة مرتبة[1, 2, 3, 4, 5, 6, 7, 8, 9].

سؤال وجواب

كيف الهرم الفرز العمل?

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

ما هي ملامح الهرم الفرز?

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

كيف يمكنني إنشاء كومة ثنائية للفرز الهرمي?

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

لماذا الفرز الهرمي فعال?

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

هل من الممكن استخدام الفرز الهرمي لفرز هياكل البيانات الأخرى?

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

هل هناك عيوب لفرز الهرم?

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