تصنيف الكومة

تصنيف الكومة (Heap sort) في علم الحاسوب هو عبارة عن خوارزمية تصنيف تعتمد على المقارنات بين القيم المختلفة. يمكن اعتبار تصنيف الكومة بأنه نسخة معدّلة من التصنيف الانتقائي، إذ يقسم كل من التصنيفين المدخلات إلى قسمين، أحدهما مرتب والآخر غير مرتب، ويقلَّل حجم القسم غير المرتب بشكل دوري ومتتابع من خلال اختيار القيمة الأعلى من بين القيم غير المرتبة وموضعتها بطريقة صحيحة في القسم المرتب.  يختلف تصنيف الكومة عن التصنيف الانتقائي من حيث الفعالية فيما يتعلق بحسابات الوقت اللازم لتصنيف وترتيب المدخلات كاملة، تصنيف الكومة لا يضيع الوقت كالتصنيف الانتقائي، وهو جيد جدًا فيما يتعلق بالسرعة، فباستخدام تصنيف الكومة يمكننا ترتيب كافة المدخلات في زمن خطيّ، من خلال اختيار العنصر ذي القيمة الأعلى في كل مرة.[1]

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

اكتشف العالم والرياضي ج. و. ج. ويليامز تصنيف الكومة في العام 1964. وفي نفس العام كان اختراع الكومة أو الكدسة كتعبير برمجي يستخدم لتخزين البيانات المختلفة وقام العالم ويليامز بتوظيف بنية المعطيات التي اخترعها من أجل تصنيف وترتيب البيانات وأظهر مدى أهمية هذه البنية. وكذلك في العام 1964، نشر العالم ر.و.فلويد نسخة معدّلة من هذا التصنيف مثبتًا أنه يمكنه ترتيب مصفوفة كاملة من البيانات دون الحاجة إلى مساحة تخزينية إضافية، ومكملًا بذلك بحثه عن الخوارزميات المستخدمة في التنصيف عند استعمال الشجر كبنية للتعبير عن المدخلات (بالإنجليزية: treesort).[3]

الخوارزمية

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

وهذه الخطوات هي:

1.    في البداية، استدعِ الاقتران ()buildMaxHeap لتطبيقه على المدخلات الأساسية الموجودة في قائمة معينة. ثم طبق الاقتران ()heapify، والذي سيبني الكومة بمقدار زمني خطي (بالإنجليزية: (O(n).

2.   استبدل العنصر الأول في القائمة بالعنصر الأخير. قلل عدد القيم المأخوذة بعين الاعتبار بمقدار وحدة واحدة.

3.   استدعِ الاقتران ()siftDown على القائمة ليتموضع العنصر الأول في القائمة في مكانه المناسب في الكومة.

4.   كرر الخطوات بدءًا بالخطوة الثانية حتى يصبح عدد القيم الموجودة في القائمة مساويًا لوحدة واحدة.

الاقتران ()buildMaxHeap ينفذ مرة واحدة فقط، وينفذ في زمن خطي مقداره (ن)، (بالإنجليزية: (O(n). أما الاقتران ()siftDown فيستهلك زمنًا مقداره (لو ن)، (بالإنجليزية: (O(lgn)، ونستقدم هذا الاقتران بعدد (ن) من المرات. بالتالي يمكن حساب أداء هذه الخوارزمية كالتالي: (ن + ن لو ن) (بالإنجليزية: (O(n + n log n). لتلخيص كل ما سبق، يمكن اعتبار أداء هذه الخوارزمية (O(n + n log n.

المراجع

  1. ^ Skiena, Steven (2008). "Searching and Sorting". The Algorithm Design Manual. Springer. صفحة 109. doi:10.1007/978-1-84800-070-4_4.  . [H]eapsort is nothing but an implementation of selection sort using the right data structure.
  2. ^ Williams 1964
  3. ^ Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. صفحة 209.  .


للمزيد حول المقال تصفح :