二分ヒープ(ヒープ木)を使ったヒープソート

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

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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]