二分ヒープ（ヒープ木）を使ったヒープソート

ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ（木）を使ってやってみた。
参考にしたページはココらへん。

　cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python
　cf. 二分ヒープ – ウィキペディア

class Node

  attr_accessor :val, :left, :right
  attr_reader :parent

  def initialize(val, parent = nil)
    @val = val
    @parent = parent
    @left = nil
    @right = nil
  end

end   # of class Node

class HeapTree

  def initialize
    @root = nil
  end

  def insert(val)
    if @root.nil?
      @root = Node.new(val)
    else
      v = vacant
      n = Node.new(val, v)
      if v.left.nil?
        v.left = n
      else
        v.right = n
      end
      upheap(n)
    end
  end

  def shift
    if @root.nil?
      nil
    else
      val = @root.val
      @root.val = delete_last
      downheap(@root)
      val
    end
  end

  def upheap(node)
    until node.parent.nil? || node.val > node.parent.val
      v = node.val
      node.val = node.parent.val
      node.parent.val = v
      node = node.parent
    end
  end

  def downheap(node)
    return nil if node.nil?
    until node.left.nil?
      if node.right.nil? || node.left.val < node.right.val
        if node.val > node.left.val
          v = node.val
          node.val = node.left.val
          node.left.val = v
          node = node.left
        else
          break
        end
      else
        if node.val > node.right.val
          v = node.val
          node.val = node.right.val
          node.right.val = v
          node = node.right
        else
          break
        end
      end
    end
  end

  def vacant
    q = [@root]
    while n = q.shift
      if n.left.nil? || n.right.nil?
        return n
      else
        q << n.left
        q << n.right
      end
    end
  end

  def last
    q = [@root]
    begin
      n = q.shift
      q << n.left if n.left
      q << n.right if n.right
    end until q.empty?
    n
  end

  def delete_last
    node = last
    if node.parent.nil?
      @root = nil
    else
      if node.parent.right == node
        node.parent.right = nil
      else
        node.parent.left = nil
      end
    end
    node.val
  end

end   # of HeapTree


if $0 == __FILE__
  ary = (1..100).to_a.sample(10)
  puts "unsorted: " + ary.inspect
  heap = HeapTree.new
  ary.each do |x|
    heap.insert(x)
  end
  sorted = []
  while v = heap.shift do
    sorted << v
  end
  puts "sorted: " + sorted.inspect
end

なんだかあんまりきれいじゃないけど。特に downheap のあたりが。 とりあえず出来たって感じ。 最初は upheap や downheap でノード自体を入れ替えようとしてたのでもっとひどかった。ノードはそのままにしておいて持っている値だけ入れ替えればいいことに気づいていくらかマシになった。 実行結果：

takatoh@nightschool $ ruby heap_sort.rb
unsorted: [75, 63, 96, 9, 21, 92, 48, 83, 51, 31]
sorted:   [9, 21, 31, 48, 51, 63, 75, 83, 92, 96]