From: Shin-ichiro HARA <sinara@...>
Date: 2005-07-28T12:30:19+09:00
Subject: [ruby-list:40949] Re: 値の集合内の中から値の大きな数個のみを取得するには？

原です。

私も採りたいものが数個なら最小値との比較で十分と思い
ます。

それが大きくかつ最終的にソートさせるなら、児玉さんの 
priority queue を使うといいかもしれません。内部でヒー
プ構造を使っています。

  http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html

require 'pqueue'

class SizedPQueue000 < PQueue
  def initialize(limit, compareProc)
    @limit = limit
    super(compareProc)
  end

  def push(x)
    if size >= @limit
      if gt.call(top, x)
        pop
        super
      end
    else
      super
    end
  end
end


que = SizedPQueue000.new(10, proc{|x, y| x < y})

n = 100000
(0...n).each do
  que.push rand(n)
end

que.each_pop do |x|
  p x
end


あれ、よく考えるとこの用途なら「最後に一回クイックソート」
でも十分ですね。