No.1ベストアンサー
- 回答日時:
#Wikipediaの「二分ヒープ - ヒープ操作」を参考に作ってみた。
#「upheap/downheap操作は次のような配列の点から説明できる。」以下は読んでも良く解らなかった。
#最初は配列だけにしていたが、追加操作や削除操作を持つクラスの方がわかりやすそうだったのでクラスにしました。(ループ変数の変数名がiからじゃなくてjからになっているのはその名残り)
#速度や計算量の測定はしていません。
class BinaryTree
def initialize
@array = []
end
def size
@array.size
end
def add(val)
if @array.size == 0
@array.push(val)
else
@array.push(val)
j = @array.size - 1
while j > 0
if @array[((j - 1) / 2).floor] > @array[j]
@array[j],@array[((j - 1) / 2).floor] = @array[((j - 1) / 2).floor], @array[j]
else
break
end
j = ((j - 1) / 2).floor
end
end
val
end
def remove
temp = @array.shift()
if @array.size != 0
@array.unshift(@array.pop())
j = 0
while 2 * j + 1 < @array.size
if 2 * j + 1 == @array.size - 1
minimum = 2 * j + 1
else
if @array[2 * j + 1] > @array[2 * j + 2]
minimum = 2 * j + 2
else
minimum = 2 * j + 1
end
end
if @array[minimum] >= @array[j]
minimum = j
end
@array[minimum],@array[j] = @array[j],@array[minimum]
if j == minimum
break
else
j = minimum
end
end
end
temp
end
def arr
@array
end
end
hoge = BinaryTree.new
myarray = [12,11,13,19,15,8,7,10]
while myarray.size != 0
p hoge.add(myarray.shift())
end
print "---\n"
p hoge.arr
print "---\n"
while hoge.size != 0
p hoge.remove()
end
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) マクロについて教えてください。 4 2023/06/06 09:06
- 数学 「違います 質問11 n≦-2ではz≠π/2で g(z)=tan(z)/(z-π/2)^(n+1) 3 2022/07/16 18:12
- Visual Basic(VBA) マクロについて教えてください。 1 2023/06/06 00:57
- Excel(エクセル) 別シートの表の値を参照したい 2 2022/03/30 15:11
- JavaScript 助けてください‼︎ javascriptで質問があります。 配列を定義して、 29342、45342 3 2022/06/26 22:06
- 数学 t=tan(x/2)の置換積分について質問です。写真の問題では、(1)でt=tan(x/2)として、 6 2022/11/21 22:59
- 数学 mtrajcp様に以前答えていただいた解答に関して、 複数の疑問がございます。 どうか、質問を連投す 3 2022/09/03 08:00
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- Excel(エクセル) エクセル VBAの構文について 2 2023/02/10 18:26
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ビーリアルのユーザー名を変え...
-
やり 直し
-
(再質問)エクセルのマクロボ...
-
パソコンのスクリーンセーバー...
-
1、Rstudioで回帰直線を求める...
-
pandasでsqlite3にテーブル作成...
-
pythonエラー
-
パイソンのクラスについて
-
WIN11にオフイスを複数入れるこ...
-
教えてください
-
パイソンエラーについて
-
プログラミングについてです。...
-
初心者プログラミング
-
Ruby on Railsでサーバーを立ち...
-
英数字を含む文字列(0-9,A-Z)...
-
ruby
-
クリスタルレポートで困ってい...
-
VBA
-
パイソンプログラミング
-
パイソンでテキストファイルが...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
pythonのerrorコード
-
What class are you in? には何...
-
パイソンのクラス
-
No route matches [GET] "/post...
-
クラス名やモジュール名の競合...
-
Rubyについて質問です
-
変数の隠蔽とは?
-
HSTLやSSTL等のI/Oピン
-
クラスの再定義について(C++)
-
redirect先でredirect元の変数...
-
Ruby ハッシュ継承クラス、作成...
-
classのdelete
-
PostScript言語で定積分の計算
-
Rubyの質問です
-
class roomとclassroom どちら...
-
テンプレートの特殊化でコンパ...
-
get() と find() の違いについて
-
「arg」は何の略?
-
エラー「メソッドまたはデータ...
-
教えてください。vb5.0
おすすめ情報