Implementation (Part 1)
Lektion 5 von 9 im Kurs Heap Sort - DSA-Serie von Coddy.
Wir werden Heap Sort von seiner Kernoperation an aufbauen.
Aufgabe
EinfachDas Herzstück von Heap Sort ist die sift-down Operation. Lassen Sie uns diese zuerst bauen.
Schreiben Sie eine Funktion namens siftDown, die ein Array arr (das als binärer Heap behandelt wird) und einen Index i entgegennimmt und die Max-Heap-Eigenschaft an diesem Knoten wiederherstellt, indem sie ihn nach unten verschiebt. Vergleichen Sie den Knoten mit seinen beiden Kindern an den Positionen 2*i + 1 und 2*i + 2; wenn das größere Kind größer ist, tauschen Sie mit ihm und fahren Sie von der Position des Kindes fort. Geben Sie das Array zurück.
Zum Beispiel gibt siftDown([1, 10, 5, 3, 2], 0) das Ergebnis [10, 3, 5, 1, 2] zurück.
Probier es selbst
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Schreibe hier den Code
*returnSize = arr_size;
return arr;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Heap Sort - DSA-Serie
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity