Tree 構造を利用したヒープ（Ruby）

ここで実装した Tree 構造を使いました。

require './tree'

class Heap < Tree
  def self.build(ar)
    raise "Argument is not Array." if ar.class != Array
    ar1 = ar.dup
    q = []
    t = Heap.new(a = ar1.shift)
    q << a
    t.build1(q, ar1)
    t
  end
  
  def build1(q, ar)
    a = q.shift
    return if ar.empty?
    add(a, a1 = ar.shift)
    q << a1
    return if ar.empty?
    add(a, a1 = ar.shift)
    q << a1
    build1(q, ar)
  end
  
  def max_heapify(nd)
    m = (get_children(nd) + [nd]).max
    return if nd == m
    exchange(nd, m)
    max_heapify(nd)
  end
  
  def build_max_heep
    last_to_root {|node| max_heapify(node)}
  end
  
  def last_to_root
    @node.reverse_each {|node| yield(node)}
  end
  
  def extract_last
    a = @node[-1]
    delete(a)
    a
  end
end

class Array
  def heapsort
    t = Heap.build(self)
    ar = []
    t.build_max_heep
    t.last_to_root do |node|
      t.exchange(t.root, node)
      a = t.extract_last rescue t.root
      ar.unshift(a)
      t.max_heapify(t.root)
    end
    ar
  end
end

if __FILE__ == $0
  ar = [3, 10, 1, 8, 5, 2, 6, 7, 4, 11, 9]
  p ar.heapsort    #=>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
end

※参考
ヒープソート - Camera Obscura