ما معنى Adaptive Heap Sort؟ شرح الترتيب الكومي المتكيّف بلغة مبسّطة
خوارزمية Adaptive Heap Sort (الترتيب الكومي المتكيّف) هي نسخة مطوّرة من خوارزمية Heap Sort التقليدية، وميزتها الجوهرية أنّها "تلاحظ" مقدار الترتيب الموجود مسبقًا في البيانات وتستغلّه. فإذا كانت المصفوفة شبه مرتّبة أصلًا، يقترب زمن تنفيذها من الزمن الخطي O(n)، بينما تظل تضمن في أسوأ الحالات الأداء نفسه الذي تضمنه Heap Sort أي O(n log n). باختصار: هي خوارزمية "حسّاسة لدرجة الفوضى" في المدخلات، تكافئك على البيانات المرتّبة جزئيًا بدل أن تعاملها كأنها عشوائية تمامًا.
لماذا لا تتكيّف Heap Sort التقليدية؟
خوارزمية Heap Sort الكلاسيكية تبني كومة (Heap) من كل العناصر ثم تستخرج الجذر تكرارًا. المشكلة أنّها تفعل ذلك بالطريقة نفسها بالضبط سواء كانت المصفوفة مرتّبة تمامًا أو مقلوبة أو عشوائية. هذا يعني أنّ زمنها دائمًا في حدود O(n log n) حتى لو أعطيتها بيانات مرتّبة سلفًا. نقول عن مثل هذه الخوارزميات إنّها غير متكيّفة (non-adaptive): لا تستفيد من أي "نظام" موجود في المدخلات.
في المقابل، هناك عائلة من الخوارزميات تُسمّى خوارزميات الترتيب المتكيّفة (Adaptive Sorting)، يتناسب زمنها مع مقدار الاضطراب في البيانات، لا مع عددها فقط. وخوارزمية Adaptive Heap Sort واحدة من أشهر أعضاء هذه العائلة، وقد قدّمها الباحثان Levcopoulos وPetersson مطلع التسعينيات.
ما المقصود بـ"الترتيب المسبق"؟
قبل فهم آلية العمل، نحتاج فكرة "مقياس الفوضى". هناك عدة مقاييس شائعة لدرجة اضطراب مصفوفة:
- عدد الانعكاسات (Inversions): عدد الأزواج التي جاءت بترتيب خاطئ. مصفوفة مرتّبة تمامًا انعكاساتها صفر.
- عدد المقاطع المرتّبة (Runs): كم سلسلة صاعدة متتالية تحتاجها لتغطية المصفوفة.
- مقياس التذبذب (Oscillation): قياس أدقّ لمدى تنقّل العناصر بعيدًا عن مواقعها الصحيحة.
الفكرة المحورية: كلما صغُر هذا المقياس، اقترب زمن Adaptive Heap Sort من O(n). هذا هو معنى "التكيّف" عمليًا.
كيف تعمل فعليًا؟
النقطة التي يغفلها كثير من الشروح السطحية أنّ Adaptive Heap Sort لا تبني كومة من المصفوفة مباشرة، بل تمرّ بخطوتين:
- بناء شجرة كارتيزية (Cartesian Tree): تُمرّ الخوارزمية على المصفوفة مرة واحدة وتبني شجرة ثنائية تعكس بنية الصعود والهبوط في القيم. بناء هذه الشجرة يكلّف O(n) فقط، وهي التي تلتقط "النظام" الموجود مسبقًا في البيانات.
- الاستخراج عبر كومة صغيرة من المرشّحين: بدل وضع كل العناصر في كومة واحدة ضخمة، تحتفظ الخوارزمية بكومة صغيرة تضمّ العناصر "المرشّحة" لتكون التالية في الترتيب (جذر الشجرة وأبناؤه). في كل خطوة تسحب الأصغر، ثم تُدخل أبناءه في الكومة. حجم هذه الكومة يبقى صغيرًا عندما تكون البيانات شبه مرتّبة، وهنا يأتي الربح في الأداء.
بهذا الأسلوب، إذا كانت المصفوفة قريبة من الترتيب، تبقى الكومة صغيرة طوال الوقت، فتقل كلفة عمليات log وتقترب النتيجة من الزمن الخطي.
Heap Sort أم Adaptive Heap Sort؟
| المعيار | Heap Sort التقليدية | Adaptive Heap Sort |
|---|---|---|
| أسوأ حالة | O(n log n) | O(n log n) |
| بيانات شبه مرتّبة | O(n log n) دائمًا | تقترب من O(n) |
| حسّاسة لترتيب المدخلات | لا | نعم |
| الذاكرة الإضافية | O(1) (في المكان) | O(n) لشجرة كارتيزية والكومة |
| الثبات (Stable) | غير ثابتة | غير ثابتة عمومًا |
| بساطة التنفيذ | بسيطة نسبيًا | أعقد |
الخلاصة من الجدول: أنت تدفع ذاكرة إضافية بقدر O(n) وبعض التعقيد في التنفيذ، مقابل مكسب حقيقي في السرعة عندما تكون بياناتك مرتّبة جزئيًا.
متى تستخدمها ومتى تتجنّبها؟
استخدمها عندما تعرف أنّ مدخلاتك "شبه مرتّبة" بطبيعتها: سجلّات زمنية تصل بترتيب شبه صحيح، بيانات مُحدَّثة تدريجيًا، أو قوائم أُعيد فرزها بعد تعديل بسيط. في هذه الحالات تتفوّق بوضوح.
تجنّبها إذا كانت بياناتك عشوائية بالكامل ولا يهمّك التكيّف؛ فلن تحصل على مكسب يُذكر، وستدفع كلفة الذاكرة الإضافية والتعقيد بلا مقابل. في المشاريع العملية غالبًا ما تكون خوارزميات مثل Timsort (المستخدمة في Python وJava للكائنات) خيارًا أنسب، لأنها متكيّفة أيضًا وجاهزة ومختبَرة داخل المكتبات القياسية.
نصيحة عملية وخطأ شائع
الخطأ الأكثر شيوعًا هو الخلط بين "المتكيّف" و"الأسرع دائمًا". Adaptive Heap Sort ليست أسرع من كل شيء في كل الحالات؛ ميزتها مشروطة بوجود ترتيب مسبق فعلي. قبل أن تستثمر في تطبيقها بنفسك، قِس درجة الاضطراب في بياناتك الحقيقية (مثلًا بحساب عدد الانعكاسات على عيّنة). فإن وجدتها منخفضة، فالتكيّف يستحق العناء؛ وإن كانت مرتفعة فأنت تعقّد الكود دون فائدة.
الأسئلة الشائعة
هل Adaptive Heap Sort خوارزمية "في المكان" (in-place)؟ لا في صورتها الكلاسيكية؛ فهي تحتاج ذاكرة إضافية بمقدار O(n) لبناء الشجرة الكارتيزية والكومة، بخلاف Heap Sort التقليدية التي تعمل في المكان.
هل هي خوارزمية ثابتة (Stable)؟ عمومًا لا. إن كان الحفاظ على الترتيب النسبي للعناصر المتساوية مهمًّا لك، ففكّر في Merge Sort أو Timsort.
ما أفضل حالاتها من حيث الزمن؟ عندما تكون المصفوفة مرتّبة أو شبه مرتّبة، يقترب الأداء من O(n)، وهو مكسب كبير مقارنةً بـ O(n log n) الثابتة لدى Heap Sort.
هل أحتاج تطبيقها بنفسي في العمل اليومي؟ نادرًا. المكتبات القياسية في اللغات الحديثة توفّر خوارزميات فرز متكيّفة مثل Timsort. Adaptive Heap Sort أهم من الناحية النظرية ولفهم مبدأ "التكيّف مع الترتيب المسبق"، أكثر من كونها أداة تكتبها من الصفر يوميًا.