Implementation (Part 1)
Coddyの「ヒープソート - DSAシリーズ」コースのレッスン 5/9。
ヒープソートを、その中心となる操作から順に構築していきます。
チャレンジ
簡単ヒープソートの核心はsift-down（シフトダウン）操作です。まずはそれを作成しましょう。
arr（バイナリヒープとして扱う配列）とインデックス i を受け取り、そのノードを下に押し下げることで最大ヒープの特性を復元する、siftDown という名前の関数を記述してください。ノードを 2*i + 1 と 2*i + 2 にある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;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
ヒープソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity