מימוש (חלק 1)

שיעור 5 מתוך 9 בקורס מיון ערימה – סדרת DSA של Coddy.

נבנה את מיון הערימה, החל מפעולת הליבה שלו.

אתגר

קל

הליבה של מיון ערימה היא פעולת sift-down. בואו נבנה אותה קודם.

כתבו פונקציה בשם siftDown שמקבלת מערך arr (שמתייחסים אליו כאל ערימה בינארית) ואינדקס i, ומשחזרת את תכונת ערימת המקסימום בצומת הזה על ידי דחיפתו כלפי מטה. השוו את הצומת לשני ילדיו במיקומים 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;
}