Implementation (Part 2)
الدرس 6 من 9 في دورة Heap Sort - سلسلة DSA على Coddy.
الآن نقوم بدمج عملية بناء الكومة واستخراج الحد الأقصى بشكل متكرر.
التحدي
متوسطالآن قم بتجميع كل ذلك في الخوارزمية الكاملة.
اكتب دالة باسم heapSort تأخذ مصفوفة من الأعداد الصحيحة وتعيدها مرتبة ترتيباً تصاعدياً.
أولاً، قم ببناء max-heap عن طريق إجراء عملية sift down لكل عقدة ليست ورقة (non-leaf node)، بدءاً من الفهرس n/2 - 1 وصولاً إلى 0. ثم قم بتبديل الجذر (أكبر قيمة) بشكل متكرر مع العنصر الأخير في الـ heap، وقم بتقليص حجم الـ heap بمقدار واحد، ثم قم بإجراء sift down للجذر الجديد مرة أخرى.
استخدم دالة مساعدة لـ sift-down تأخذ حجم الـ heap الحالي
size، حتى تتمكن من تقليص الـ heap أثناء العمل.
جرّب بنفسك
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, int* returnSize) {
// اكتب الكود هنا
*returnSize = arr_size;
return arr;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس Heap Sort - سلسلة DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity