プログラミング歴約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
↑自分で実装したヒープ構造です。
機能は要素の追加と取り出しのみです。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/03/02 06:47