Implementation (Part 2)

Lektion 6 von 9 im Kurs Heap Sort - DSA-Serie von Coddy.

Nun kombinieren wir den Aufbau des Heaps und das wiederholte Extrahieren des Maximums.

Aufgabe

Mittel

Füge nun alles zum vollständigen Algorithmus zusammen.

Schreibe eine Funktion namens heapSort, die ein Ganzzahl-Array entgegennimmt und es in aufsteigender Reihenfolge sortiert zurückgibt.

Erstelle zuerst einen Max-Heap, indem du jeden Nicht-Blatt-Knoten von Index n/2 - 1 bis hinunter zu 0 nach unten siffst (sift down). Vertausche dann wiederholt die Wurzel (den größten Wert) mit dem letzten Element des Heaps, verkleinere den Heap um eins und siffe die neue Wurzel wieder nach unten.

Verwende eine Sift-Down-Hilfsfunktion, die die aktuelle Heap-size entgegennimmt, damit du den Heap während des Vorgangs verkleinern kannst.

Probier es selbst

#include <stdlib.h>

int* heapSort(int* arr, int arr_size, int* returnSize) {
    // Schreibe den Code hier
    *returnSize = arr_size;
    return arr;
}

Teste dich selbst

Diese 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

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Projekt-Lektion

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2