تصنيف الكومة

تصنيف الكومة (بالإنجليزية: Heap sort)‏ في علم الحاسوب هو عبارة عن خوارزمية تصنيف تعتمد على المقارنات بين القيم المختلفة. يمكن اعتبار تصنيف الكومة بأنه نسخة معدّلة من التصنيف الانتقائي، إذ يقسم كل من التصنيفين المدخلات إلى قسمين، أحدهما مرتب والآخر غير مرتب، ويقلَّل حجم القسم غير المرتب بشكل دوري ومتتابع من خلال اختيار القيمة الأعلى من بين القيم غير المرتبة وموضعتها بطريقة صحيحة في القسم المرتب. يختلف تصنيف الكومة عن التصنيف الانتقائي من حيث الفعالية فيما يتعلق بحسابات الوقت اللازم لتصنيف وترتيب المدخلات كاملة، تصنيف الكومة لا يضيع الوقت كالتصنيف الانتقائي، وهو جيد جدًا فيما يتعلق بالسرعة، فباستخدام تصنيف الكومة يمكننا ترتيب كافة المدخلات في زمن خطيّ، من خلال اختيار العنصر ذي القيمة الأعلى في كل مرة. رغم أن تصنيف الكومة قد يكون بطيئًا في مسائل معينة وعلى أجهزة معينة إذا ما قورن بالتصنيف السريع، فله حسنةً خاصةً به، وهي أن الزمن الأسوأ والأطول اللازم لحساب أية مسألة لا يمكن أن يتجاوز (ن لو ن) ( وبالإنجليزية: ( O(n log n). بالإصافة إلى ذلك، يعمل تصنيف الكومة بترتيب المدخلات دون الحاجة إلى مساحة تخزينية إضافية، فهو يوجد النتيجة المرجوة وتصنيفها في نفس المساحة التخزينية المحجوزة مسبقًا لتخزين المدخلات، لكن تصنيف الكومة لا يمكن اعتباره تصنيفًا ثابتًا. اكتشف العالم والرياضي ج. و. ج. ويليامز تصنيف الكومة في العام 1964. وفي نفس العام كان اختراع الكومة أو الكدسة كتعبير برمجي يستخدم لتخزين البيانات المختلفة وقام العالم ويليامز بتوظيف بنية المعطيات التي اخترعها من أجل تصنيف وترتيب البيانات وأظهر مدى أهمية هذه البنية. وكذلك في العام 1964، نشر العالم ر.و.فلويد نسخة معدّلة من هذا التصنيف مثبتًا أنه يمكنه ترتيب مصفوفة كاملة من البيانات دون الحاجة إلى مساحة تخزينية إضافية، ومكملًا بذلك بحثه عن الخوارزميات المستخدمة في التنصيف عند استعمال الشجر كبنية للتعبير عن المدخلات (بالإنجليزية: treesort).