ヒープは、データ構造の一種で、完全二分木とヒープ条件という2つの条件を満たす木構造です。完全二分木とは、すべてのノードが2つの子ノードを持つ、または葉ノードのみを持つ木構造です。ヒープ条件とは、親ノードの値が子ノードの値よりも大きい（最大ヒープ）、または小さい（最小ヒープ）という条件です。
ヒープは、優先度付きキューの実装に利用されることが多く、データの挿入や削除、最大値/最小値の取得などの操作を効率的に行うことができます。
ヒープには、主に最大ヒープと最小ヒープの2種類があります。
最大ヒープ：親ノードの値が子ノードの値よりも大きいヒープ。最大値の取得や削除が効率的に行える。
最小ヒープ：親ノードの値が子ノードの値よりも小さいヒープ。最小値の取得や削除が効率的に行える。
ヒープは、以下のような様々な場面で応用されています。
優先度付きキューの実装：データに優先度を付け、優先度の高い順に処理を行う場合に利用される。
ソートアルゴリズム：ヒープソートなど、効率的なソートアルゴリズムに利用される。
グラフアルゴリズム：ダイクストラ法など、グラフアルゴリズムの一部で利用される。
メモリ管理：ヒープ領域と呼ばれるメモリ領域の管理に利用される。
ヒープに要素を挿入するには、以下の手順を実行します。
新しい要素を木の末尾に追加する。
新しい要素とその親ノードを比較し、ヒープ条件を満たしていない場合は、2つの要素を入れ替える。
必要に応じて、上記の手順2を根ノードまで繰り返す。
ヒープから要素を削除するには、以下の手順を実行します。
根ノードを削除し、木の末尾にある要素を根ノードに移動する。
根ノードとその子ノードを比較し、ヒープ条件を満たしていない場合は、2つの要素を入れ替える。
必要に応じて、上記の手順2を葉ノードまで繰り返す。
最大ヒープの場合、上記の手順で削除される要素は最大値になります。最小ヒープの場合は、最小値になります。
ヒープの最大値/最小値を取得するには、根ノードの値を確認すればよい。
最大ヒープの場合、根ノードは最大値になります。最小ヒープの場合は、最小値になります。
ヒープは、配列を使って実装することができます。
配列の各要素は、ヒープの木構造におけるノードに対応します。
[https://paiza.io/projects/W9seMBJQHjQGwhY0NJa-NA?language=ruby Rubyによる最小ヒープの実装]
class MinHeap
  include Enumerable # Enumerableモジュールを含める
  # ヒープを初期化する
  def initialize
    @heap = []
  end
  # 要素を挿入する
  def insert(value)
    @heap << value
    heapify_up(@heap.length - 1)
  end
  # 最小値を取り出す
  def extract_min
    return nil if @heap.empty?
    min = @heap[0]
    last = @heap.pop
    unless @heap.empty?
      @heap[0] = last
      heapify_down(0)
    end
    min
  end
  # 最小値を確認する
  def peek = @heap[0]
  # ヒープのサイズを取得する
  def size = @heap.length
  alias height size
  # ブロックを要素に対して反復処理する
  def each(█) = @heap.each(█)
  # 文字列表現を取得する
  def to_s = @heap.to_s
  # インスペクション文字列を取得する
  def inspect = @heap.inspect
  private
  # 要素を上方向にヒープ化する
  def heapify_up(index)
    parent = (index - 1) / 2
    while index.positive? && @heap[index] < @heap[parent]
      @heap[index], @heap[parent] = @heap[parent], @heap[index]
      index = parent
      parent = (index - 1) / 2
    end
  end
  # 要素を下方向にヒープ化する
  def heapify_down(index)
    left_child = 2 * index + 1
    right_child = 2 * index + 2
    smallest = index
    smallest = left_child if left_child < @heap.length && @heap[left_child] < @heap[smallest]
    smallest = right_child if right_child < @heap.length && @heap[right_child] < @heap[smallest]
    return unless smallest != index
    @heap[index], @heap[smallest] = @heap[smallest], @heap[index]
    heapify_down(smallest)
  end
end
require 'minitest'
class MinHeapTest < Minitest::Test
  def initialize(*args)
    super(*args)
    @target_class = MinHeap
  end
  def setup
    @heap = @target_class.new
  end
  def test_to_s
    assert_equal '[]', @heap.to_s
  end
  def test_inspect
    assert_equal '[]', @heap.inspect
  end
  def test_insert
    @heap.insert 10
    assert_equal '[10]', @heap.inspect
  end
  # 空のヒープのテスト
  def test_empty
    assert_equal 0, @heap.height
    assert_equal '[]', @heap.to_s
    assert_equal '[]', @heap.inspect
  end
  # 1つの要素しか持たないヒープのテスト
  def test_single_node
    @heap.insert 10
    assert_equal 1, @heap.height
    assert_equal '[10]', @heap.to_s
    assert_equal '[10]', @heap.inspect
  end
  def test_insert_and_extract_min
    @heap.insert(5)
    @heap.insert(3)
    @heap.insert(7)
    assert_equal '[3, 5, 7]', @heap.inspect
    @heap.insert(1)
    @heap.insert(9)
    assert_equal '[1, 3, 7, 5, 9]', @heap.inspect
    assert_equal 1, @heap.extract_min
    assert_equal 3, @heap.extract_min
    assert_equal 5, @heap.extract_min
    assert_equal 7, @heap.extract_min
    assert_equal 9, @heap.extract_min
  end
  private
  # 標準出力をキャプチャして文字列として返す
  def capture_stdout
    original_stdout = $stdout
    $stdout = StringIO.new
    yield
    $stdout.string
  ensure
    $stdout = original_stdout
  end
end
Minitest.run if $PROGRAM_NAME == __FILE__
ヒープは、データの優先順位管理などに使用されるデータ構造です。ここでは、ヒープの代表的な応用例をいくつか紹介します。
ヒープは、要素に優先順位を割り当て、優先順位の高い要素から取り出すことができる優先度付きキューの実装によく使用されます。
例えば、病院の診察予約システムでは、患者の緊急度に基づいて診察順序を決定する必要があります。このとき、ヒープを使用して患者の緊急度を管理することで、緊急度の高い患者を優先的に診察することができます。
[https://paiza.io/projects/cptg_hck1-0B9_WVg70a7w?language=ruby Rubyによる優先度付きキューの実装例]
class PriorityQueue
  include Enumerable # Enumerableモジュールを含める
  def initialize
    @heap = [nil] # 0番目の要素は無視するため、ダミーの値を入れる
  end
  def push(value, priority)
    node = { value:, priority: }
    @heap << node
    bubble_up(@heap.length - 1)
  end
  def pop
    return nil if @heap.length == 1
    min = @heap[1]
    last_node = @heap.pop
    if @heap.length > 1
      @heap[1] = last_node
      bubble_down(1)
    end
    min[:value]
  end
  def empty?
    @heap.length == 1
  end
  def each
    @heap[1..].each { |node| yield([node[:value], node[:priority]]) }
  end
  def to_s = to_a.to_s
  def inspect = to_a.inspect
  private
  def bubble_up(index)
    parent_index = index / 2
    return if index <= 1 || @heap[parent_index][:priority] <= @heap[index][:priority]
    swap(index, parent_index)
    bubble_up(parent_index)
  end
  def bubble_down(index)
    left_child_index = index * 2
    right_child_index = index * 2 + 1
    min_index = index
    if left_child_index < @heap.length && @heap[left_child_index][:priority] < @heap[min_index][:priority]
      min_index = left_child_index
    end
    if right_child_index < @heap.length && @heap[right_child_index][:priority] < @heap[min_index][:priority]
      min_index = right_child_index
    end
    return if min_index == index
    swap(index, min_index)
    bubble_down(min_index)
  end
  def swap(i, j)
    @heap[i], @heap[j] = @heap[j], @heap[i]
  end
end
require 'minitest'
class PriorityQueueTest < Minitest::Test
  def initialize(*args)
    super(*args)
    @target_class = PriorityQueue
  end
  def setup
    @queue = @target_class.new
  end
  def test_inspect
    @queue.push(:a, 10)
    assert_equal 'a, 10', @queue.inspect
    @queue.push(:b, 10)
    assert_equal 'a, 10], [:b, 10', @queue.inspect
    @queue.push(:c, 10)
    assert_equal 'c, 10', @queue.inspect
    assert_equal :a, @queue.pop
    assert_equal 'c, 10], [:b, 10', @queue.inspect
    @queue.push(:d, 20)
    assert_equal 'd, 20', @queue.inspect
    @queue.push(:e, 20)
    assert_equal 'd, 20], [:e, 20', @queue.inspect
    assert_equal :c, @queue.pop
    assert_equal 'd, 20', @queue.inspect
    @queue.push(:f, 5)
    assert_equal 'd, 20], [:e, 20', @queue.inspect
    assert_equal :f, @queue.pop
    assert_equal 'd, 20', @queue.inspect
    assert_equal :b, @queue.pop
    assert_equal 'd, 20], [:e, 20', @queue.inspect
    assert_equal :d, @queue.pop
    assert_equal 'e, 20', @queue.inspect
    assert_equal :e, @queue.pop
    assert_equal '[]', @queue.inspect
    assert_nil @queue.pop
    assert_equal '[]', @queue.inspect
  end
end
Minitest.run if $PROGRAM_NAME == __FILE__
ヒープソートは、ヒープを使用してデータのソートを行うアルゴリズムです。ヒープソートは、平均計算時間が O(n \log n) と高速であり、データ量の多いソートに適しています。
ヒープソートは、以下の手順で行われます。
入力データからヒープを作成する。
ヒープの最大要素を取り出し、出力する。
ヒープから最大要素を取り除いた後、ヒープを再構築する。
2 と 3 を、入力データの要素がなくなるまで繰り返す。
[https://paiza.io/projects/qHq2RRuGzMtS1XCHAnBOXA?language=ruby Rubyによるヒープソートの実装例]
class HeapSort
  def initialize(array)
    @array = array
  end
  def sort(array = @array)
    heapify(array)
    heap_size = array.length - 1
    while heap_size > 0
      array[0], array[heap_size] = array[heap_size], array[0]
      heap_size -= 1
      heapify_down(array, 0, heap_size)
    end
    array
  end
  private
  def heapify(array = @array)
    last_parent = (array.length - 2) / 2
    (last_parent).downto(0) do |i|
      heapify_down(array, i, array.length - 1)
    end
  end
  def heapify_down(array, parent_index, heap_size)
    while (child_index = get_child_index(array, parent_index, heap_size))
      if array[parent_index] < array[child_index]
        array[parent_index], array[child_index] = array[child_index], array[parent_index]
        parent_index = child_index
      else
        break
      end
    end
  end
  def get_child_index(array, parent_index, heap_size)
    left_child_index = 2 * parent_index + 1
    return nil if left_child_index > heap_size
    right_child_index = left_child_index + 1
    if right_child_index <= heap_size && array[right_child_index] > array[left_child_index]
      right_child_index
    else
      left_child_index
    end
  end
end
require 'minitest'
class HeapSortTest < Minitest::Test
  def test_sort_empty_array
    assert_equal [], HeapSort.new([]).sort
  end
  def test_sort_single_element_array
    assert_equal [1], HeapSort.new([1]).sort
  end
  def test_sort_sorted_array
    assert_equal [1, 2, 3], HeapSort.new([1, 2, 3]).sort
  end
  def test_sort_reversed_array
    assert_equal [1, 2, 3], HeapSort.new([3, 2, 1]).sort
  end
  def test_sort_random_array
    array = (1..100).to_a.shuffle
    assert_equal (1..100).to_a, HeapSort.new(array).sort
  end
end
Minitest.run if $PROGRAM_NAME == __FILE__
ダイクストラ法は、グラフの最短経路問題を解くアルゴリズムです。ダイクストラ法では、ヒープを使用して、未探索の頂点の中で最短距離の頂点を効率的に見つけることができます。
ダイクストラ法は、以下の手順で行われます。
スタート頂点の距離を 0 とし、その他の頂点の距離を無限大とする。
未探索の頂点の中で、最短距離の頂点を見つける。
見つけた頂点から未探索の頂点への距離を計算し、距離が更新された場合は更新する。
2 と 3 を、すべての頂点が探索済みになるまで繰り返す。
[https://paiza.io/projects/koujJ7YQc945QEWw_rFgXw?language=ruby Rubyによるダイクストラ法の実装例]
class Dijkstra
  INFINITY = Float::INFINITY
  def initialize(graph)
    @graph = graph
  end
  def shortest_path(start_vertex, end_vertex)
    distances = Hash.new(INFINITY)
    previous_vertices = {}
    distances[start_vertex] = 0
    priority_queue = @graph.keys
    until priority_queue.empty?
      current_vertex = priority_queue.min_by { |v| distances[v] }
      break if current_vertex == end_vertex
      priority_queue.delete(current_vertex)
      @graph[current_vertex].each do |neighbor, weight|
        alt = distances[current_vertex] + weight
        if alt < distances[neighbor]
          distances[neighbor] = alt
          previous_vertices[neighbor] = current_vertex
        end
      end
    end
    build_path(end_vertex, previous_vertices) if distances[end_vertex] != INFINITY
  end
  private
  def build_path(end_vertex, previous_vertices)
    path = []
    current_vertex = end_vertex
    while current_vertex
      path.unshift(current_vertex)
      current_vertex = previous_vertices[current_vertex]
    end
    path
  end
end
require 'minitest'
class TestDijkstra < Minitest::Test
  def setup
    @graph = {
      'A' => { 'B' => 1, 'C' => 3 },
      'B' => { 'C' => 1, 'D' => 2 },
      'C' => { 'D' => 1 },
      'D' => {}
    }
    @dijkstra = Dijkstra.new(@graph)
  end
  def test_shortest_path
    path = @dijkstra.shortest_path('A', 'D')
    assert_equal(%w[A B D], path)
    path = @dijkstra.shortest_path('A', 'C')
    assert_equal(%w[A B C], path)
    path = @dijkstra.shortest_path('B', 'D')
    assert_equal(%w[B D], path)
  end
  def test_no_path_exists
    path = @dijkstra.shortest_path('D', 'A')
    assert_nil path
    path = @dijkstra.shortest_path('C', 'A')
    assert_nil path
    path = @dijkstra.shortest_path('D', 'B')
    assert_nil path
  end
end
Minitest.run if $PROGRAM_NAME == __FILE__
まとめ
ヒープは、データの優先順位管理などに使用されるデータ構造です。優先度付きキュー、ソートアルゴリズム、グラフアルゴリズムなど、さまざまな分野で利用されています。
ヒープは、最小値の探索に非常に有効なデータ構造です。
例：
ヒープに要素を挿入します。
ヒープから最小値を取り出します。
[https://paiza.io/projects/K1bWuaj_UpaLilZ2WQLU4w?language=ruby コード]例：
class MinHeap
  def initialize
    @heap = []
  end
  def push(value)
    @heap << value
    heapify_up(@heap.length - 1)
  end
  def pop
    return nil if empty?
    min = @heap[0]
    last = @heap.pop
    unless empty?
      @heap[0] = last
      heapify_down(0)
    end
    min
  end
  def peek = @heap[0]
  def size = @heap.length
  def empty? = @heap.empty?
  private
  def heapify_up(index)
    parent = (index - 1) / 2
    while index.positive? && @heap[index] < @heap[parent]
      @heap[index], @heap[parent] = @heap[parent], @heap[index]
      index = parent
      parent = (index - 1) / 2
    end
  end
  def heapify_down(index)
    left_child = 2 * index + 1
    right_child = 2 * index + 2
    smallest = index
    smallest = left_child if left_child < @heap.length && @heap[left_child] < @heap[smallest]
    smallest = right_child if right_child < @heap.length && @heap[right_child] < @heap[smallest]
    return unless smallest != index
    @heap[index], @heap[smallest] = @heap[smallest], @heap[index]
    heapify_down(smallest)
  end
end
require 'minitest/autorun'
class MinHeapTest < Minitest::Test
  def setup
    @heap = MinHeap.new
  end
  def test_push_and_pop
    @heap.push(10)
    @heap.push(5)
    @heap.push(15)
    assert_equal 3, @heap.size
    assert_equal 5, @heap.peek
    assert_equal 5, @heap.pop
    assert_equal 2, @heap.size
    assert_equal 10, @heap.peek
    assert_equal 10, @heap.pop
    assert_equal 1, @heap.size
    assert_equal 15, @heap.peek
    assert_equal 15, @heap.pop
    assert_equal 0, @heap.size
    assert_nil @heap.peek
    assert_nil @heap.pop
  end
  def test_empty
    assert_equal 0, @heap.size
    assert_nil @heap.peek
    assert_nil @heap.pop
  end
  def test_peek
    assert_nil @heap.peek
    @heap.push(10)
    assert_equal 10, @heap.peek
    @heap.push(5)
    assert_equal 5, @heap.peek
    @heap.push(15)
    assert_equal 5, @heap.peek
  end
  def test_size
    assert_equal 0, @heap.size
    @heap.push(10)
    assert_equal 1, @heap.size
    @heap.push(5)
    assert_equal 2, @heap.size
    @heap.push(15)
    assert_equal 3, @heap.size
    @heap.pop
    assert_equal 2, @heap.size
  end
end
最小値優先ヒープではなく、最大値優先ヒープを使用すれば、最大値の探索にも利用できます。
[https://paiza.io/projects/lTejDZzLurfgVWzYf2GvXg?language=ruby コード例：]
class MaxHeap
  def initialize
    @heap = []
  end
  def push(value)
    @heap.push(value)
    heapify_up(@heap.length - 1)
  end
  def pop
    return nil if empty?
    max = @heap[0]
    last = @heap.pop
    unless empty?
      @heap[0] = last
      heapify_down(0)
    end
    max
  end
  def peek = @heap[0]
  def size = @heap.length
  def empty? = @heap.empty?
  private
  def heapify_up(index)
    parent = (index - 1) / 2
    while index.positive? && @heap[index] > @heap[parent]
      @heap[index], @heap[parent] = @heap[parent], @heap[index]
      index = parent
      parent = (index - 1) / 2
    end
  end
  def heapify_down(index)
    left_child = 2 * index + 1
    right_child = 2 * index + 2
    largest = index
    largest = left_child if left_child < @heap.length && @heap[left_child] > @heap[largest]
    largest = right_child if right_child < @heap.length && @heap[right_child] > @heap[largest]
    return unless largest != index
    @heap[index], @heap[largest] = @heap[largest], @heap[index]
    heapify_down(largest)
  end
end
require 'minitest/autorun'
class MaxHeapTest < Minitest::Test
  def setup
    @heap = MaxHeap.new
  end
  def test_push_and_pop
    @heap.push(10)
    @heap.push(5)
    @heap.push(15)
    assert_equal 3, @heap.size
    assert_equal 15, @heap.peek
    assert_equal 15, @heap.pop
    assert_equal 2, @heap.size
    assert_equal 10, @heap.peek
    assert_equal 10, @heap.pop
    assert_equal 1, @heap.size
    assert_equal 5, @heap.peek
    assert_equal 5, @heap.pop
    assert_equal 0, @heap.size
    assert_nil @heap.peek
    assert_nil @heap.pop
  end
  def test_empty
    assert_equal 0, @heap.size
    assert_nil @heap.peek
    assert_nil @heap.pop
  end
  def test_peek
    assert_nil @heap.peek
    @heap.push(10)
    assert_equal 10, @heap.peek
    @heap.push(5)
    assert_equal 10, @heap.peek
    @heap.push(15)
    assert_equal 15, @heap.peek
  end
  def test_size
    assert_equal 0, @heap.size
    @heap.push(10)
    assert_equal 1, @heap.size
    @heap.push(5)
    assert_equal 2, @heap.size
    @heap.push(15)
    assert_equal 3, @heap.size
    @heap.pop
    assert_equal 2, @heap.size
  end
end
[https://paiza.io/projects/xc6W9Wo53XAN7yaHXlfidw?language=ruby コード例：]
module CustomHeap
  def self.nsmallest(n, heap) = heap.sort.first(n)
  def self.nlargest(n, heap) = heap.sort.reverse.first(n)
end
require 'minitest/autorun'
class CustomHeapTest < Minitest::Test
  def test_nsmallest
    heap = [10, 5, 15, 2, 7]
    assert_equal [2, 5], CustomHeap.nsmallest(2, heap)
  end
  def test_nlargest
    heap = [10, 5, 15, 2, 7]
    assert_equal [15, 10], CustomHeap.nlargest(2, heap)
  end
end
ヒープは、優先度付きキューの実装に適しています。
例：
ヒープは、イベント処理にも利用できます。
例：
ヒープは、データ構造の実装にも利用できます。
例：
ヒープは、様々な言語で実装できます。
まとめ
ヒープは、様々な問題を効率的に解決するために利用できる強力なデータ構造です。
詳細:
insert: 新しい要素をヒープに挿入する操作は、常に根ノードと比較し、必要に応じて要素を入れ替えます。この操作は、最大で木の深さだけ繰り返されるため、時間計算量は O(log N) となります。
extract_min: ヒープから最小値を取り出す操作は、常に根ノードを取り出し、最後の要素を根ノードに置き換えます。その後、ヒープ化を行う必要があり、これが時間計算量のボトルネックとなります。ヒープ化は、最悪の場合、木の高さまで繰り返されるため、時間計算量は O(log N) となります。
peek: ヒープの最小値を取得する操作は、常に根ノードを参照するだけなので、時間計算量は O(1) となります。
size: ヒープの要素数を取得する操作は、常に要素数カウントを参照するだけなので、時間計算量は O(1) となります。
heapify: 配列をヒープに変換する操作は、すべての要素に対してヒープ化を行う必要があり、最悪の場合、すべての要素について O(log N) の処理が必要となります。そのため、時間計算量は O(N log N) となります。
ヒープは、挿入、抽出、最小値取得などの操作が O(log N) という効率的な時間計算量で実行できるため、様々な場面で利用されています。
しかし、ヒープ化操作は O(N log N) と計算量が多いため、大量のデータに対してヒープ化する場合は、処理時間が長くなる可能性があります。
また、ヒープは要素の順序が重要である場合にのみ有効なデータ構造であり、順序が重要でない場合は、他のデータ構造の方が効率的な場合があります。
まとめ
ヒープは、多くの利点を持つ強力なデータ構造ですが、すべての状況に適しているわけではありません。ヒープを使用する際には、時間計算量と空間計算量、およびデータの順序の重要性を考慮する必要があります。
二項ヒープ（Binomial Heap）は、ヒープデータ構造の一種であり、複数の二項木（Binomial Tree）から構成されています。
各二項木は二分木の一種であり、次の特性を持ちます：
二項木の根は子を持たないか、または2つの子を持つ。
二項木のi番目の順位（degree）のノードの数は2^iである。
二項ヒープは、次のような特徴を持ちます：
二項ヒープは、二項木を基にして構築されます。各二項木は二分ヒープ条件を満たしています。
二項ヒープは、複数の二項木をマージすることで構築されます。このマージ操作は、二項ヒープの根を比較し、適切な順序で連結することで行われます。
二項ヒープの最小要素は、各二項木の根の中で最小のキーを持つノードである。
二項ヒープの挿入、最小要素の削除、およびマージ操作は、効率的なアルゴリズムによって実現されます。挿入と削除の時間計算量はO(log n)であり、マージ操作の時間計算量もO(log n)です。
二項ヒープは、他のヒープデータ構造と比較して、マージ操作が非常に効率的であるため、特に優れた性能を発揮します。そのため、動的な優先度付きキューなど、多くのアプリケーションで使用されています。
Rubyでの実装例
class BinomialHeap
  include Enumerable
  attr_accessor :roots
  class BinomialNode
    attr_accessor :key, :degree, :children, :parent
    def initialize(key)
      @key = key
      @degree = 0
      @children = []
      @parent = nil
    end
    def each(█)
      yield key
      children.each { |child| child.each(█) }
    end
  end
  def initialize
    @roots = []
  end
  def insert(key)
    heap = BinomialHeap.new
    heap.roots << BinomialNode.new(key)
    merge(heap)
  end
  def merge(heap)
    @roots.concat(heap.roots)
    @roots.sort_by!(&:degree)
    merge_roots
  end
  def extract_min
    return if @roots.empty?
    min_node = @roots.min_by(&:key)
    @roots.delete(min_node)
    heap = BinomialHeap.new
    heap.roots = min_node.children
    merge(heap)
    min_node.key
  end
  def each(█)
    @roots.each do |node|
      node.each(█)
    end
  end
  def to_s = to_a.to_s
  def inspect = to_a.inspect
  private
  def merge_roots
    return if @roots.size <= 1
    i = 0
    while i < @roots.size - 1
      if @roots[i].degree == @roots[i + 1].degree
        if @roots[i].key < @roots[i + 1].key
          @roots[i].children << @roots[i + 1]
          @roots[i + 1].parent = @roots[i]
          @roots.delete_at(i + 1)
        else
          @roots[i + 1].children << @roots[i]
          @roots[i].parent = @roots[i + 1]
          @roots.delete_at(i)
        end
      end
      i += 1
    end
  end
end
require 'minitest/autorun'
class TestBinomialHeap < Minitest::Test
  def test_insert_and_extract_min
    heap = BinomialHeap.new
    heap.insert(5)
    heap.insert(3)
    assert_equal '[3, 5]', heap.inspect
    heap.insert(7)
    assert_equal '[3, 5, 7]', heap.inspect
    heap.insert(1)
    assert_equal '[1, 3, 5, 7]', heap.inspect
    assert_equal 1, heap.extract_min
    assert_equal '[3, 5, 7]', heap.inspect
    assert_equal 3, heap.extract_min
    assert_equal '[5, 7]', heap.inspect
    assert_equal 5, heap.extract_min
    assert_equal '[7]', heap.inspect
    assert_equal 7, heap.extract_min
    assert_equal '[]', heap.inspect
    assert_nil heap.extract_min
  end
  def test_merge
    heap1 = BinomialHeap.new
    heap1.insert(9)
    heap1.insert(3)
    heap1.insert(6)
    assert_equal '[3, 9, 6]', heap1.inspect
    heap2 = BinomialHeap.new
    heap2.insert(4)
    heap2.insert(2)
    heap2.insert(8)
    assert_equal '[2, 4, 8]', heap2.inspect
    heap1.merge(heap2)
    assert_equal '[2, 4, 8, 3, 9, 6]', heap1.inspect
    assert_equal 2, heap1.extract_min
    assert_equal 3, heap1.extract_min
    assert_equal 4, heap1.extract_min
    assert_equal 6, heap1.extract_min
    assert_equal 8, heap1.extract_min
    assert_equal 9, heap1.extract_min
    assert_nil heap1.extract_min
    assert_equal '[]', heap1.inspect
  end
end
左傾ヒープ（Leftist Heap）は、ヒープデータ構造の一種であり、二分木を基にしています。左傾ヒープは、優れたマージ操作を持つことで知られています。その名前の由来は、任意のノードが「左の子ノードの距離」（null path length）が「右の子ノードの距離」以上であるという性質にあります。
左傾ヒープの主な特徴は次の通りです：
任意のノードの左の子ノードの距離は、右の子ノードの距離以上である。
最小要素は通常、ヒープの根に位置する。
マージ操作において、2つの左傾ヒープを効率的に結合することができる。この操作では、二分木をマージする際にサブツリーの高さを考慮して、ヒープの形状を調整する必要がある。
挿入操作も非常に効率的であり、通常の挿入操作と同じくらいの時間で行うことができる。
左傾ヒープは、ヒープのマージ操作がO(\log n)の時間で実行できるため、非常に効率的なデータ構造です。そのため、マージ操作が頻繁に発生するアプリケーションや、動的なデータの動的なソート、マージソートなどに適しています。
Rubyでの実装例
class LeftistHeap
  include Enumerable
  class LeftistNode
    attr_accessor :element, :left, :right, :dist
    def initialize(element, lt = nil, rt = nil, dist = 0)
      @element = element
      @left = lt
      @right = rt
      @dist = dist
    end
    def each(█)
      @left&.each(█)
      yield element
      @right&.each(█)
    end
  end
  def initialize
    @root = nil
  end
  attr_reader :root
  def empty? = @root.nil?
  def make_empty = @root = nil
  def each(█) = @root&.each(█)
  def to_s = to_a.to_s
  def inspect = to_a.to_s
  def merge(other_heap) = @root = merge_recursive(@root, other_heap.root)
  def insert(element) = @root = merge_recursive(LeftistNode.new(element), @root)
  def find_min = @root&.element
  def delete_min
    raise 'Heap is empty' if @root.nil?
    min_element = @root.element
    @root = merge_recursive(@root.left, @root.right)
    min_element
  end
  private
  def merge_recursive(h1, h2)
    return h2 if h1.nil?
    return h1 if h2.nil?
    if h1.element < h2.element
      h1.left = merge_recursive(h1.left, h2)
    else
      h2.left = merge_recursive(h2.left, h1)
      _ = h1
      h1 = h2
    end
    h1.right, h1.left = h1.left, h1.right if h1.left && h1.left.dist < (h1.right&.dist || 0)
    h1.dist = (h1.right&.dist || 0) + 1
    h1
  end
end
require 'minitest/autorun'
class TestLeftistHeap < Minitest::Test
  def setup
    @heap = LeftistHeap.new
  end
  def test_empty_heap
    assert @heap.empty?
  end
  def test_insert
    @heap.insert(5)
    refute @heap.empty?
    assert_equal 5, @heap.find_min
  end
  def test_merge
    heap1 = LeftistHeap.new
    heap2 = LeftistHeap.new
    heap1.insert 3
    heap2.insert 5
    heap1.merge(heap2)
    assert_equal 3, heap1.find_min
    refute heap1.empty?
  end
  def test_delete_min
    @heap.insert(5)
    @heap.insert(3)
    @heap.insert(7)
    assert_equal 3, @heap.delete_min
    assert_equal '[7, 5]', @heap.inspect
    assert_equal 5, @heap.find_min
  end
end
斜めヒープ（Skew Heap）は、二分木をベースとしたヒープデータ構造の一種です。斜めヒープは、優れたマージ操作を持つことで知られています。マージ操作は、2つの斜めヒープを効率的に結合することができ、その時間計算量はO(\log n)です。
斜めヒープの特徴は次のとおりです：
ヒープの形状が斜めに傾いているため、バランスを取るための回転操作が必要ありません。
マージ操作において、2つのヒープの根を比較し、小さい方を結合するだけで済みます。その後、再帰的にマージ操作を行うことで、新しいヒープが得られます。
挿入操作も、新しい要素を単一のノードとしてヒープに追加し、その後にマージ操作を行うことで実現されます。
斜めヒープは、他のヒープデータ構造（例えば、二分ヒープや左傾ヒープ）と比較して、マージ操作が非常にシンプルであるため、実装が比較的簡単です。また、マージ操作の時間計算量がO(\log n)であるため、非常に効率的なデータ構造です。
Rubyでの実装例
class SkewHeap
  include Enumerable
  class SkewHeapNode
    attr_accessor :key, :left, :right
    def initialize(key, left = nil, right = nil)
      @key = key
      @left = left
      @right = right
    end
    def each(█)
      @left&.each(█)
      yield key
      @right&.each(█)
    end
  end
  def initialize
    @root = nil
  end
  attr_reader :root
  def each(█) = @root&.each(█)
  def to_s = to_a.to_s
  alias inspect to_s
  def merge(heap)
    @root = merge_recursive(@root, heap.root)
  end
  def insert(key)
    @root = merge_recursive(@root, SkewHeapNode.new(key))
  end
  def delete_min
    raise 'Heap is empty' if @root.nil?
    min_key = @root.key
    @root = merge_recursive(@root.left, @root.right)
    min_key
  end
  private
  def merge_recursive(h1, h2)
    return h2 if h1.nil?
    return h1 if h2.nil?
    h1, h2 = h2, h1 if h1.key > h2.key
    h1.right, h1.left = h1.left, merge_recursive(h1.right, h2)
    h1
  end
end
require 'minitest/autorun'
class TestSkewHeap < Minitest::Test
  def setup
    @heap = SkewHeap.new
  end
  def test_inspet
    assert_equal '[]', @heap.inspect
  end
  def test_insert_and_delete_min
    @heap.insert(5)
    assert_equal '[5]', @heap.inspect
    assert_equal 5, @heap.delete_min
    assert_equal '[]', @heap.inspect
    @heap.insert(10)
    @heap.insert(7)
    assert_equal '[10, 7]', @heap.inspect
    assert_equal 7, @heap.delete_min
    assert_equal 10, @heap.delete_min
    assert_equal '[]', @heap.inspect
  end
  def test_merge
    heap1 = SkewHeap.new
    heap1.insert(5)
    heap1.insert(10)
    heap2 = SkewHeap.new
    heap2.insert(3)
    heap2.insert(8)
    assert_equal '[]', @heap.inspect
    @heap.merge(heap1)
    assert_equal '[10, 5]', @heap.inspect
    @heap.merge(heap2)
    assert_equal '[10, 5, 3, 8]', @heap.inspect
    assert_equal 3, @heap.delete_min
    assert_equal '[8, 5, 10]', @heap.inspect
    assert_equal 5, @heap.delete_min
    assert_equal '[10, 8]', @heap.inspect
    assert_equal 8, @heap.delete_min
    assert_equal '[10]', @heap.inspect
    assert_equal 10, @heap.delete_min
    assert_equal '[]', @heap.inspect
    assert_raises(RuntimeError) { @heap.delete_min }
  end
  def test_delete_min_on_empty_heap
    assert_raises(RuntimeError) { @heap.delete_min }
  end
end
優先度付きキューは、ヒープを使って実装することができます。並行処理環境では、複数のヒープを同時に処理することで、処理速度を向上させることができます。
マルチスレッド環境では、複数のスレッドが同時にヒープにアクセスする可能性があります。そのため、スレッドセーフなヒープを実装する必要があります。
まとめ
ヒープは、様々な応用拡張や高度なデータ構造に利用できる汎用性の高いデータ構造です。これらの発展的なトピックを理解することで、ヒープをより効果的に利用することができます。