0801006ヒープソート

ソーティングと順序統計量

• ソートは基本で重要だよ
• ソーティング問題
  • 入力は単独の数であると仮定
  • もっとも基本的な問題
    • 工学的な要因により、アルゴリズムなどの選択を行う

ヒープソート

• マージソートと同じ実行時間
  • O(n lg n)
• 挿入ソートより速い
• 挿入ソートと同じその場ソーティング

ヒープ構造

• 優先度キューの効率の良い実現方法
• 後半で出る、max-heap-insert 等で説明
• Java/Lisp の GC の記憶容量の「ヒープ」とは別の意味
• 本書のヒープは、ヒープのデータ構造で

コード

実際に疑似コードを Ruby で実装

Ruby の配列への[]のアクセスは、アルゴリズムイントロダクションの擬似コードの配列 -1 なので、 アルゴリズムイントロダクションと同じ挙動をする HArray を定義する

class HArray < DelegateClass(Array)
  attr_accessor :heap_size
  def initialize(a = [])
    super(a)
    self.heap_size = a.length
  end
  def [](key)
    __getobj__[key-1]
  end
  def []=(key, val)
    __getobj__[key-1]= val
  end
end

# Array[0] == HArray[1]

ヒープ

• 完全二分木として見なすことのできる配列
  • 図を書く
• 添え字iから、木構造の親、左の子、右の子がわかる

def parent(i)
  i / 2
end
def left(i)
  2 * i
end
def right(i)
  2 * i + 1
end

二分木ヒープの種類

• max ヒープ
  • 親は子以上(maxヒープ条件)
• min ヒープ
  • 親は子以下(minヒープ条件)
  • 優先度付きキューではこちらがよく使われる
• ヒープの高さ
• シータ(lg n)

maxヒープの実装

実装・max_heapify

まずは max_heapify.

指定した添え字と子が、max-heap な構造になるように滑り落とす

def max_heapify(a, i)
  l = left(i)
  r = right(i)
  if l <= a.heap_size && a[l] > a[i]
    then largest = l
    else largest = i ;end
  if r <= a.heap_size && a[r] > a[largest]
    then largest = r ;end
  if largest != i
    then a[i], a[largest] = a[largest], a[i]
      max_heapify(a, largest) ;end; end

# P125
a = HArray.new([16,4,10,14,7,9,3,2,8,1])
max_heapify(a, 2)
p a

実装・ヒープの構成 build_max_heapify

ボトムアップで max_heapify を利用することで、max ヒープを構築することができるよ

def build_max_heap(a)
  a.heap_size = a.length
  for i in (a.length/2).downto 1
    max_heapify(a, i) ;end ;end

# P127
a = HArray.new([4,1,3,2,16,9,10,14,8,7])
build_max_heap(a)
p a

P128 で、build_max_heap のコストは O(n) なので、未ソートのときからmax_heap を線形時間で構成可能だよ

いよいよヒープソート

• max_heap は、先頭が最大値
• 最大値を取り除く
  • 配列の一番最後と交換
  • heap_size を一個小さく (一番最後が無視)
  • もう一度maxヒープを構築するよ
    • 一番親を、max_heapify するだけでよい

def heap_sort(a)
  build_max_heap(a)
  a.heap_size = a.length
  for i in a.length.downto 2
    a[1], a[i] = a[i], a[1]
    a.heap_size = a.heap_size - 1
    max_heapify(a, 1) ;end ;end

# P130
a = HArray.new([4,1,3,2,16,9,10,14,8,7])
heap_sort(a)
p a

優先度付きキュー

• ヒープ構造を使って実装
  • ジョブキューなど
• max ヒープ構造
  • 一番先頭が、一番大きい数
  • max ヒープが構築できれば、priority が高いものほど先に実行できるキューが！
• 優先度つきキューの、max ヒープ構築時間は O(lg n)

優先度付きキューの実装

キーの値を大きい値に変更し、max_heap を構築

def heap_increse_key(a, i, key)
  if key < a[i]
    then raise '新しいは現在のキーより小さい' ;end
  a[i] = key
  while i > 1 && a[parent(i)] < a[i]
    a[i], a[parent(i)] = a[parent(i)], a[i]
    i = parent(i) ;end ;end

ヒープを一つ増やし、max_heap を構築

def max_heap_insert(a, key)
  a.heap_size = a.heap_size + 1
  a[a.heap_size] = -Float::MAX
  heap_increse_key(a, a.heap_size, key); end

まとめ

• ヒープ構造すごい
  • ヒープソート
  • 優先度付きキュー

終わりに