ヒープソート - Camera Obscura

破壊的メソッドになります。

class Array
  #要素iから下へ、maxヒープ状態が満たされるようにselfを修復する
  def max_heapify(i)
    l = 2 * i  + 1
    r = l + 1
    largest = (l <= @heap_size - 1 and self[l] > self[i]) ? l : i
    largest = r if r <= @heap_size - 1 and self[r] > self[largest]
    return if largest == i
    self[i], self[largest] = self[largest], self[i]
    max_heapify(largest)
  end
  
  #maxヒープを構築する
  def build_max_heap
    @heap_size = size
    (size / 2 - 1).downto(0) {|i| max_heapify(i)}
  end
  
  def heapsort
    build_max_heap
    (size - 1).downto(1) do |i|
      self[0], self[i] = self[i], self[0]
      @heap_size -= 1
      max_heapify(0)
    end
    self
  end
end

a = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
p a.heapsort    #=>[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

max 優先度付きキュー。優先度付きキュー（優先度付き待ち行列）は、プライオリティキュー（priority queue）とも呼ばれます。

class Array
  #要素iの親の要素を返す
  def parent(i)
    (i + 1) / 2 - 1
  end

  #selfの最大のキー値を返す
  def heap_maximum
    self[0]
  end
  
  #selfから最大のキーをもつ要素を削除し、その要素を返す
  def heap_extract_max
    raise "heap underflow" if !@heapsize or @heap_size < 1
    maximum = shift
    @heap_size -= 1
    max_heapify(0)
    maximum
  end
  alias :dequeue :heap_extract_max
  
  #要素iのキーを新しいキー値keyに変更してselfを修復　ただしkeyは要素iのキー値以上である
  def heap_increase_key(i, key)
    raise "New key is smaller than the present key." if key < self[i]
    self[i] = key
    while i > 0 and self[parent(i)] < self[i]
      self[i], self[parent(i)] = self[parent(i)], self[i]
      i = parent(i)
    end
  end
  
  #selfの最後にキー値keyを挿入して、selfを修復する
  def max_heap_insert(key)
    @heap_size = size + 1
    self[@heap_size - 1] = - Float::INFINITY
    heap_increase_key(@heap_size - 1, key)
  end
  alias :enqueue :max_heap_insert
end