heapq

標準でないのかな？？？
なのでpythonから引っ張ってくる。
Arrayに突っ込む。

class Array
  
  def heappush(item)
    self.push(item)
    siftdown(0, self.length - 1)
  end
  
  def heappop
    lastelt = self.pop()
    if self.length > 0
        returnitem = self[0]
        self[0] = lastelt
        siftup(0)
    else
        returnitem = lastelt
    end
    return returnitem
  end
  
  def heapify
    n = self.length
    (n/2).downto(0){|x|
      siftup(x)
    }
  end

  private
  def siftdown(startpos, pos)
    newitem = self[pos]
    while pos > startpos
        parentpos = (pos - 1) >> 1
        parent = self[parentpos]
        if newitem < parent
            self[pos] = parent
            pos = parentpos
            next
        end
        break
    end
    self[pos] = newitem
  end

  private
  def siftup(pos)
    endpos = self.length
    startpos = pos
    newitem = self[pos]
    childpos = 2*pos + 1
    while childpos < endpos
        rightpos = childpos + 1
        if rightpos < endpos and not self[childpos] < self[rightpos]
            childpos = rightpos
        end
        
        self[pos] = self[childpos]
        pos = childpos
        childpos = 2*pos + 1
    end
    self[pos] = newitem
    siftdown(startpos, pos)
    return nil
  end 

end

bisect(bsearch)は確か高林さんが作ったのがあったな。