Implementation (Part 1)
الدرس 5 من 9 في دورة Heap Sort - سلسلة DSA على Coddy.
سنقوم ببناء خوارزمية Heap Sort بدءاً من عمليتها الأساسية.
التحدي
سهلقلب خوارزمية Heap Sort هو عملية sift-down. لنقم ببناء ذلك أولاً.
اكتب دالة باسم siftDown تأخذ مصفوفة arr (تُعامل كـ binary heap) وفهرس i، وتستعيد خاصية الـ max-heap عند تلك العقدة عن طريق دفعها للأسفل. قارن العقدة مع طفليها عند 2*i + 1 و 2*i + 2؛ إذا كان الطفل الأكبر أكبر منها، فقم بالتبديل معه واستمر من موضع الطفل. أعد المصفوفة.
على سبيل المثال، siftDown([1, 10, 5, 3, 2], 0) تُرجع [10, 3, 5, 1, 2].
جرّب بنفسك
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, 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