ヒープ（バイナリヒープ）

Good Math, Bad Math : Binary Heaps
ヒープは、スタックやキューと並びシンプルで強力なデータ構造です。ヒープとは、木構造の一種で要素の挿入と最大値（又は最小値）の要素の削除の計算量が共にO(logN)。このヒープを2分木で表現したものを、バイナリヒープと呼びます。バイナリヒープの場合、要素の挿入と削除が行われると、常に根ノードと最大値の要素が常に等しくなるよう、ノードの入れ替えが行われます。
このようなヒープの性質は、優先順位付きキューなど、何らかの基準値によって要素が順位付けされた集合を表現するデータ構造に向いています。また、仕組みが単純な分、実装が容易な点も魅力的です。
恐らく多くの方々にとって、ヒープは一般的なアルゴリズムの教科書で説明されているように、整列プログラムを実装するためのデータ構造としてよく知られているのではないでしょうか。上のヒープの性質を応用すれば、簡単に配列の要素を整列出来ることがすぐに分かるでしょう。すなわち、配列から一つずつ要素を取り出してヒープに挿入すれば、後から自然と要素が整列された順番でヒープから要素が取り出すことが出来ます（なんて簡単！）。
ヒープソートの計算量は、ヒープの挿入と削除の計算量はO(logN)なので、Ｎ個の要素を整列する場合、O(NlogN + NlogN) = O(NlogN) です。代表的な整列アルゴリズムであるクイックソートの場合、平均計算量はO(NlogN)ですが、配列を分割するピボットの選び方によって最悪の場合O(N^2)かかる傾向があります。これに対して、ヒープソートは平均と最悪の場合で変わらず常にO(NlogN)しかかかりません。ただし、空間効率という点においてヒープソートは、ヒープを構築するために最低で元の配列の2倍のメモリサイズが必要なので、他の整列アルゴリズムに劣ります。しかし、PCのメモリ資源が潤沢な現在、計算コスト＞空間コスト のような状況においては、ヒープソートの採用は十分に検討する価値があると思います。
以下は、バイナリヒープのサンプルプログラムです。こちらで紹介されているソースコードをRubyで再実装してみました。参考にどうぞ。

class Heap
  
  def initialize
    @list = []
  end

  def insert(value)
    @list << value
    if @list.length > 1
      last = @list.length - 1
      bubble_up(last)      
    end
  end
  
  def remove_largest
    root = @list.shift
    bubble_down(0)
    root
  end
  
  def to_s
    "[#{@list.join(',')}]"
  end  
  
  private
  
  def parent_of(pos)
    if pos == 0
      nil
    elsif pos == 1 || pos == 2
      0
    else
      if pos % 2 == 0
        (pos - 2)/2
      else
        (pos - 1)/2
      end  
    end
    
  end
  
  def children_of(pos)
    n = @list.length
    left = 2*pos + 1
    right = 2*pos + 2
    if n <= left
      []
    elsif n == right
      [left]
    else
      [left, right]      
    end
  end  

  def swap(i, j)
    tmp = @list[i]
    @list[i] = @list[j]
    @list[j] = tmp
  end
  
  def bubble_up(pos)
    unless pos == 0
      parent = parent_of(pos)
      if @list[parent] < @list[pos]
        swap(parent, pos)
        bubble_up(parent)
      end            
    end    
  end
  
  def bubble_down(pos)
    children = children_of(pos)
    unless children.empty?
      if children.length == 1
        i = children[0]
        if @list[pos] < @list[i]
          swap(pos, i)
          bubble_down(i)
        end
      else
        (i, j) = children
        left = @list[i]
        right = @list[j]
        root = @list[pos]
        if (left > root) || (right > root)
          if left > right
            swap(i, pos)
            bubble_down(i)
          else
            swap(j, pos)
            bubble_down(j)
          end
        end
      end
    end
  end
  
end

def heap_use_example
  heap = Heap.new

  heap.insert(1)
  heap.insert(3)
  heap.insert(5)
  heap.insert(7)
  heap.insert(9)
  p heap.to_s

  list = []
  list << heap.remove_largest
  p heap.to_s
  list << heap.remove_largest
  p heap.to_s
  list << heap.remove_largest
  p heap.to_s
  list << heap.remove_largest
  p heap.to_s
  list << heap.remove_largest
  p heap.to_s

  p list.join(',')  
end

heap_use_example