Implementation (Part 2)
Coddyの「ヒープソート - DSAシリーズ」コースのレッスン 6/9。
ここでは、ヒープの構築と最大値の抽出の繰り返しを組み合わせます。
チャレンジ
中級それでは、すべてを組み合わせて完全なアルゴリズムを作成しましょう。
整数の配列を受け取り、それを昇順にソートして返す heapSort という名前の関数を作成してください。
まず、インデックス n/2 - 1 から 0 までのすべての非リーフノードを sift-down することで、最大ヒープ（max-heap）を構築します。次に、ルート（最大値）をヒープの最後の要素と繰り返し入れ替え、ヒープのサイズを1つ縮小し、新しいルートを再び sift-down します。
ヒープを進行に合わせて縮小できるように、現在のヒープの
sizeを引数に取る sift-down ヘルパー関数を使用してください。
自分で試してみよう
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, int* returnSize) {
// ここにコードを記述してください
*returnSize = arr_size;
return arr;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
ヒープソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity