2018.09.01 プログラミング・PC関連shirabelog

ヒープソートのメモ

みなさんご機嫌いかがでしょうか。アルゴリズムの授業で学んだヒープソートですが、いまいち飲み込めていないので後学のために学習の記録をここに残します。

Heap Sort： close to Complete Binary Tree as an Array

Let a[1], a[2],a[3]~a[n]The root node・・・a[1]Node i・・・a[i](子の添字をiとした場合)Parent of Node i・・・a[i/2]※a[i/2]はfloorで整数になることに注意。たとえば、i = 3のとき、つまりa[3]のとき、Parent of Node i はa[3/2]・・・a[1]となる。
(親の添字をiとした場合)Left of Node i・・・a[2i](親の添字をiとした場合)Right of Node i・・・a[2i+1]※Left of Node がRight of Nodeより先に埋まるため。

if a[i] has both children, then とりうるiの範囲は
1≦ 2i+1 ≦ n
1≦ 2i ≦ n-1
1≦ i ≦(n-1)/2
※本来であれば、1/2 ≦ iとなるが　nの取りうる値は整数であることから1≦ i となる。
※Right of Node iのとりうる範囲を求める。

if a[i] only have left child, then とりうるiの範囲は
1≦ 2i≦ n
1≦ i≦ n/2
※ただし、Right of Node iと重複する範囲を除く必要があるから、
(n-1)/2 < i ≦ n/2

if a[i] has no child, then とりうるiの範囲は
n< 2i
n/2<i
※ただし、とりうる値は最大でnなので
n/2 < i ≦ n

今日はこんな感じです！

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [単行本（ソフトカバー）]

渡部有隆

マイナビ

2015-01-30

本ブログをご覧頂き誠にありがとうございます。みなさまの支えがあってブログを継続更新できています。たまにはクリック頂けますと幸いです！

にほんブログ村

にほんブログ村