ヒープソート・優先度付きキュー
この演習では、ヒープソートと優先度付きキューについて学び、各手法をC言語で実装する方法について学びます。
問題の難易度の目安【易】⭐ 【標準】⭐⭐【難】⭐⭐⭐
ヒープソートの理解は順を追って理解する必要があります。 まずは木構造・ヒープについて理解しましょう。 こちらの動画が参考になると思います。
問題1⭐
要素数nのヒープが格納されている配列において、 入力した値のインデックスの親と子のインデックスを表示するプログラムを作成しましょう。
./a.out 3
と実行すると、入力されたインデックスは3となり、
parent idx: 1
children idx: 6, 7
と表示されます。
Note
要素数nは十分大きいとします。 インデックスとして与える値は2以上とします。
問題2⭐⭐⭐
要素数nのヒープが格納されている配列において、 葉のみを表示するプログラムを完成しましょう。
./a.out 16 14 10 8 7 9 3 2 4 1
と実行すれば，
9 3 2 4 1
と表示されるはずです。
Warning
配列のインデックスは0からはじまりますが、ヒープは1からはじまります。 配列のサイズが5の場合、インデックスは0から4が使われます。 ヒープのサイズが5の場合、インデックス1から5が使われます。
問題3⭐⭐⭐
ヒープ条件の維持のアルゴリズムにしたがって， 与えられた部分木をヒープにするプログラムを作成します。
部分木の場所(3)と配列を引数にして、
./a.out 3 27 17 3 16 13 10 1 5 7 12 4 8 9 0
と実行すると
27 17 3 16 13 10 1 5 7 12 4 8 9 0
27 17 10 16 13 3 1 5 7 12 4 8 9 0
27 17 10 16 13 9 1 5 7 12 4 8 3 0
27 17 10 16 13 9 1 5 7 12 4 8 3 0
と表示されるはずです。
Note
授業で習った，Max-Heapifyについて学ぶ．
問題4⭐⭐⭐
ヒープの構成のアルゴリズムにしたがって、 引数として与えられた数列をヒープにするプログラムです。
./a.out 4 1 3 2 16 9 10 14 8 7
と数列を引数として渡して実行すると、
16 14 10 8 7 9 3 2 4 1
と表示されます。
プログラムが動作するように、プログラムを完成させましょう。
Note
授業で習った，Build-Max-Heapについて学ぶ．
問題5⭐⭐
ヒープソートのアルゴリズムにしたがって、 引数として与えられた数列をヒープにし、ソートするプログラムです。
./a.out 4 1 3 2 16 9 10 14 8 7
と数列を引数として渡して実行すると、
1 2 3 4 7 8 9 10 14 16
と表示されます。
プログラムを完成しましょう。
Note
授業で習った、HeapSortについて学ぶ．
問題6⭐⭐
Heap-Maximumのアルゴリズムにしたがって、 最大のキーを返すプログラムです。
./a.out 4 1 3 2 16 9 10 14 8 7
と数列を引数として渡して実行すると、
16
と表示されます。
Note
授業で習った，heap-maximumについて学ぶ．
問題7⭐⭐
Heap-Extract-Maxにしたがって， 最大のキーを持つ要素を削除し，その要素を返すプログラムです．
./a.out 4 1 3 2 16 9 10 14 8 7
と数列を引数として渡して実行すると、
Max is 16 and extracted
14 8 10 4 7 9 3 2 1
と表示されるはずです。
プログラムが動作するように、プログラムを完成させましょう。
Note
授業で習った，Heap-Extract-Maxについて学ぶ．
問題8⭐⭐⭐
Heap-Increase-Keyのアルゴリズムにしたがって、 要素x番目の値を新しいキー値kに変更するプログラムです。
要素9番目の値を新しい値15にして実行すれば，
./a.out 9 15 4 1 3 2 16 9 10 14 8 7
というように、要素9番目の値を新しい値15、残りを数列として渡して実行すると、
16 15 10 14 7 9 3 2 8 1
と表示するはずです。
プログラムが動作するように、プログラムを完成させましょう。
Note
授業で習った，Heap-Increase-Keyについて学ぶ．
問題9⭐⭐⭐
Max-Heap-Insertのアルゴリズムにしたがって， 優先度付きキューに要素xを挿入するプログラムです。
./a.out 15 4 1 3 2 16 9 10 14 8 7
というように、挿入する要素を15として実行すれば、
16 15 10 8 14 9 3 2 4 1 7
と表示します。
プログラムが動作するように、プログラムを完成させましょう。
Note
授業で習った，Insertについて学ぶ．
問題10⭐⭐⭐
優先度付きキューからk番目に大きな値を返すプログラムを作りましょう。
./a.out 5 4 1 3 2 16 9 10 14 8 7
というように、5番目を指定して実行すれば、
Kth largest number is 8
と表示されます。