質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

Q&A

解決済

1回答

797閲覧

{Ruby} 「最小」ヒープを「最大」ヒープにしたい

nyantama

総合スコア11

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

0グッド

1クリップ

投稿2021/03/02 05:14

プログラミング歴約1年の初心者です。

Rubyで最小ヒープを実装してみました。

これを最大ヒープにするには、クラスの中の比較演算子をすべて逆にすることで実現できますが、もっと効率の良い方法を探しています。
僕のイメージとしては、rubyの標準メソッドである、sortメソッドでは↓のようにブロックを渡すことで、比較方法を変更できます。
このようなメソッドを自分で定義するには、どうすればよいでしょうか?
また、他に良い方法や、コードの改善点なんかもあれば、教えてもらえると嬉しいです。
難しい用語などは自分で頑張って調べますので、ご回答よろしくお願いします!

ruby

1array.sort {|a, b| a <=> b} 2my_heap = Heap.new {|a, b| b <=> a} 3# ↑これが理想!

ruby

1# 最小ヒープ(小さい順に要素を取り出す) 2class Heap 3 attr_accessor :cont 4 def initialize 5 @cont = [] 6 end 7 8# 要素を追加 9 def push(x) 10 @cont << x 11 i = @cont.size - 1 12 13 while true 14 j = i / 2 15 if @cont[i] < @cont[j] 16 @cont[i], @cont[j] = @cont[j], @cont[i] 17 i, j = j, j / 2 18 else 19 break 20 end 21 end 22 end 23 24# 要素を取り出す 25 def pop 26 result = @cont.shift 27 28# 取り出したあとのヒープ再構築 29 if temp = @cont.pop 30 @cont.unshift(temp) 31 32 i = 0 33 left = 1 34 right = 2 35 while true 36 if @cont[left] && @cont[right] 37 if @cont[left] <= @cont[right] && @cont[left] < @cont[i] 38 @cont[i], @cont[left] = @cont[left], @cont[i] 39 i = left 40 left, right = 2*left + 1, 2*left + 2 41 elsif @cont[right] < @cont[left] && @cont[right] < @cont[i] 42 @cont[i], @cont[right] = @cont[right], @cont[i] 43 i = right 44 left, right = 2*right + 1, 2*right + 2 45 else 46 break 47 end 48 elsif @cont[left] && @cont[left] < @cont[i] 49 @cont[i], @cont[left] = @cont[left], @cont[i] 50 break 51 else 52 break 53 end 54 end 55 end 56 result 57 end 58end 59

↑自分で実装したヒープ構造です。
機能は要素の追加と取り出しのみです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

ruby

1 def initialize(&comp) 2 @cont = [] 3 @comp = comp || proc{|a, b| a <=> b} 4 end

こんな風に比較用のブロックを受け取るようにして、この@comp.call(a, b)を使って比較すれば求める機能が実装できるはずです。

ruby

1#sample 2class Comparator 3 def initialize(&comp) 4 @comp = comp || proc{|a, b| a <=> b}#デフォルトは通常通りの比較 5 end 6 def min(a, b) 7 if (@comp.call(a, b) < 0) 8 a 9 else 10 b 11 end 12 end 13 def max(a, b) 14 if (@comp.call(a, b) > 0) 15 a 16 else 17 b 18 end 19 end 20end 21comp = Comparator.new#デフォルト 22rev = Comparator.new{|a, b| b <=> a}#反転 23p [comp.min(10, 20), rev.min(10, 20)] #=> [10, 20] 24p [comp.max(10, 20), rev.max(10, 20)] #=> [20, 10]

投稿2021/03/02 05:58

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

nyantama

2021/03/02 06:47

ありがとうございます!できました!!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問