ヒープ

ヒープの概要

ヒープの定義と特徴

ヒープは、データ構造の一種で、完全二分木とヒープ条件という2つの条件を満たす木構造です。完全二分木とは、すべてのノードが2つの子ノードを持つ、または葉ノードのみを持つ木構造です。ヒープ条件とは、親ノードの値が子ノードの値よりも大きい（最大ヒープ）、または小さい（最小ヒープ）という条件です。

ヒープは、優先度付きキューの実装に利用されることが多く、データの挿入や削除、最大値/最小値の取得などの操作を効率的に行うことができます。

ヒープの種類

ヒープには、主に最大ヒープと最小ヒープの2種類があります。

• 最大ヒープ：親ノードの値が子ノードの値よりも大きいヒープ。最大値の取得や削除が効率的に行える。
• 最小ヒープ：親ノードの値が子ノードの値よりも小さいヒープ。最小値の取得や削除が効率的に行える。

ヒープの応用例

ヒープは、以下のような様々な場面で応用されています。

• 優先度付きキューの実装：データに優先度を付け、優先度の高い順に処理を行う場合に利用される。
• ソートアルゴリズム：ヒープソートなど、効率的なソートアルゴリズムに利用される。
• グラフアルゴリズム：ダイクストラ法など、グラフアルゴリズムの一部で利用される。
• メモリ管理：ヒープ領域と呼ばれるメモリ領域の管理に利用される。

ヒープの基本操作

要素の挿入

ヒープに要素を挿入するには、以下の手順を実行します。

1. 新しい要素を木の末尾に追加する。
2. 新しい要素とその親ノードを比較し、ヒープ条件を満たしていない場合は、2つの要素を入れ替える。
3. 必要に応じて、上記の手順2を根ノードまで繰り返す。

要素の削除（最大値または最小値の取得）

ヒープから要素を削除するには、以下の手順を実行します。

1. 根ノードを削除し、木の末尾にある要素を根ノードに移動する。
2. 根ノードとその子ノードを比較し、ヒープ条件を満たしていない場合は、2つの要素を入れ替える。
3. 必要に応じて、上記の手順2を葉ノードまで繰り返す。

最大ヒープの場合、上記の手順で削除される要素は最大値になります。最小ヒープの場合は、最小値になります。

要素の取得（最大値または最小値の確認）

ヒープの最大値/最小値を取得するには、根ノードの値を確認すればよい。

最大ヒープの場合、根ノードは最大値になります。最小ヒープの場合は、最小値になります。

ヒープの実装

配列による実装方法

ヒープは、配列を使って実装することができます。

配列の各要素は、ヒープの木構造におけるノードに対応します。

• 親ノードのインデックス：i
• 左子ノードのインデックス：2i + 1
• 右子ノードのインデックス：2i + 2

ヒープ操作の詳細（要素の挿入、削除、取得などのアルゴリズム）

Rubyによる最小ヒープの実装

# frozen_string_literal: true

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(&block) = @heap.each(&block)

  # 文字列表現を取得する
  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__

ヒープの応用

ヒープは、データの優先順位管理などに使用されるデータ構造です。ここでは、ヒープの代表的な応用例をいくつか紹介します。

優先度付きキューとしての利用

ヒープは、要素に優先順位を割り当て、優先順位の高い要素から取り出すことができる優先度付きキューの実装によく使用されます。

例えば、病院の診察予約システムでは、患者の緊急度に基づいて診察順序を決定する必要があります。このとき、ヒープを使用して患者の緊急度を管理することで、緊急度の高い患者を優先的に診察することができます。

Rubyによる優先度付きキューの実装例

# frozen_string_literal: true

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 '[[:a, 10], [:b, 10], [:c, 10]]', @queue.inspect
    assert_equal :a, @queue.pop
    assert_equal '[[:c, 10], [:b, 10]]', @queue.inspect
    @queue.push(:d, 20)
    assert_equal '[[:c, 10], [:b, 10], [:d, 20]]', @queue.inspect
    @queue.push(:e, 20)
    assert_equal '[[:c, 10], [:b, 10], [:d, 20], [:e, 20]]', @queue.inspect
    assert_equal :c, @queue.pop
    assert_equal '[[:b, 10], [:e, 20], [:d, 20]]', @queue.inspect
    @queue.push(:f, 5)
    assert_equal '[[:f, 5], [:b, 10], [:d, 20], [:e, 20]]', @queue.inspect
    assert_equal :f, @queue.pop
    assert_equal '[[:b, 10], [:e, 20], [: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)$ と高速であり、データ量の多いソートに適しています。

ヒープソートは、以下の手順で行われます。

1. 入力データからヒープを作成する。
2. ヒープの最大要素を取り出し、出力する。
3. ヒープから最大要素を取り除いた後、ヒープを再構築する。

   2 と 3 を、入力データの要素がなくなるまで繰り返す。

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__

グラフアルゴリズムでの利用（ダイクストラ法など）

ダイクストラ法は、グラフの最短経路問題を解くアルゴリズムです。ダイクストラ法では、ヒープを使用して、未探索の頂点の中で最短距離の頂点を効率的に見つけることができます。

ダイクストラ法は、以下の手順で行われます。

1. スタート頂点の距離を 0 とし、その他の頂点の距離を無限大とする。
2. 未探索の頂点の中で、最短距離の頂点を見つける。
3. 見つけた頂点から未探索の頂点への距離を計算し、距離が更新された場合は更新する。

   2 と 3 を、すべての頂点が探索済みになるまで繰り返す。

Rubyによるダイクストラ法の実装例

# frozen_string_literal: true

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__

まとめ

ヒープは、データの優先順位管理などに使用されるデータ構造です。優先度付きキュー、ソートアルゴリズム、グラフアルゴリズムなど、さまざまな分野で利用されています。

ヒープの実践的な応用

ヒープを用いた問題の解法

最小値の探索

ヒープは、最小値の探索に非常に有効なデータ構造です。

例：

1. ヒープに要素を挿入します。
2. ヒープから最小値を取り出します。

コード例：

# frozen_string_literal: true

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
</code>

==== 最大値の探索 ====
最小値優先ヒープではなく、最大値優先ヒープを使用すれば、最大値の探索にも利用できます。

;[https://paiza.io/projects/lTejDZzLurfgVWzYf2GvXg?language=ruby コード例：]
:<syntaxhighlight lang=ruby>
# frozen_string_literal: true

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

最小/最大のK個の要素の取得

コード例：

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

実際のプログラムでの使用例

優先度付きキュー

ヒープは、優先度付きキューの実装に適しています。

例：

• ネットワークパケットの処理
• ジョブスケジューリング

イベント処理

ヒープは、イベント処理にも利用できます。

例：

• シミュレーション
• ゲーム開発

データ構造

ヒープは、データ構造の実装にも利用できます。

例：

• 二分木
• グラフ

ヒープの実装

ヒープは、様々な言語で実装できます。

• Python: heapq モジュール
• C++: std::priority_queue
• Java: PriorityQueue クラス

まとめ

ヒープは、様々な問題を効率的に解決するために利用できる強力なデータ構造です。

ヒープの時間計算量と空間計算量の解析

ヒープ操作の効率性と限界の議論

時間計算量

操作	時間計算量
insert	$O(logN)$
extract_min	$O(logN)$
peek	$O(1)$
size	$O(1)$
heapify	$O(N)$

空間計算量

操作	空間計算量
ヒープ	$O(N)$

詳細:

• insert: 新しい要素をヒープに挿入する操作は、常に根ノードと比較し、必要に応じて要素を入れ替えます。この操作は、最大で木の深さだけ繰り返されるため、時間計算量は $O(logN)$ となります。
• extract_min: ヒープから最小値を取り出す操作は、常に根ノードを取り出し、最後の要素を根ノードに置き換えます。その後、ヒープ化を行う必要があり、これが時間計算量のボトルネックとなります。ヒープ化は、最悪の場合、木の高さまで繰り返されるため、時間計算量は $O(logN)$ となります。
• peek: ヒープの最小値を取得する操作は、常に根ノードを参照するだけなので、時間計算量は $O(1)$ となります。
• size: ヒープの要素数を取得する操作は、常に要素数カウントを参照するだけなので、時間計算量は $O(1)$ となります。
• heapify: 配列をヒープに変換する操作は、すべての要素に対してヒープ化を行う必要があり、最悪の場合、すべての要素について $O(logN)$ の処理が必要となります。そのため、時間計算量は $O(NlogN)$ となります。

ヒープ操作の効率性と限界の議論

ヒープは、挿入、抽出、最小値取得などの操作が $O(logN)$ という効率的な時間計算量で実行できるため、様々な場面で利用されています。

しかし、ヒープ化操作は $O(NlogN)$ と計算量が多いため、大量のデータに対してヒープ化する場合は、処理時間が長くなる可能性があります。

また、ヒープは要素の順序が重要である場合にのみ有効なデータ構造であり、順序が重要でない場合は、他のデータ構造の方が効率的な場合があります。

まとめ

ヒープは、多くの利点を持つ強力なデータ構造ですが、すべての状況に適しているわけではありません。ヒープを使用する際には、時間計算量と空間計算量、およびデータの順序の重要性を考慮する必要があります。

ヒープの発展的なトピック

ヒープの応用拡張

二項ヒープ

二項ヒープ（Binomial Heap）は、ヒープデータ構造の一種であり、複数の二項木（Binomial Tree）から構成されています。

各二項木は二分木の一種であり、次の特性を持ちます：

1. 二項木の根は子を持たないか、または2つの子を持つ。
2. 二項木のi番目の順位（degree）のノードの数は2^iである。

二項ヒープは、次のような特徴を持ちます：

1. 二項ヒープは、二項木を基にして構築されます。各二項木は二分ヒープ条件を満たしています。
2. 二項ヒープは、複数の二項木をマージすることで構築されます。このマージ操作は、二項ヒープの根を比較し、適切な順序で連結することで行われます。
3. 二項ヒープの最小要素は、各二項木の根の中で最小のキーを持つノードである。
4. 二項ヒープの挿入、最小要素の削除、およびマージ操作は、効率的なアルゴリズムによって実現されます。挿入と削除の時間計算量は$O(logn)$であり、マージ操作の時間計算量も$O(logn)$です。

二項ヒープは、他のヒープデータ構造と比較して、マージ操作が非常に効率的であるため、特に優れた性能を発揮します。そのため、動的な優先度付きキューなど、多くのアプリケーションで使用されています。

Rubyでの実装例

# frozen_string_literal: true

# 二項ヒープクラスの定義
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(&block)
      yield key
      children.each { |child| child.each(&block) }
    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(&block)
    @roots.each do |node|
      node.each(&block)
    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

# Minitestを使ったテスト
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）が「右の子ノードの距離」以上であるという性質にあります。

左傾ヒープの主な特徴は次の通りです：

1. 任意のノードの左の子ノードの距離は、右の子ノードの距離以上である。
2. 最小要素は通常、ヒープの根に位置する。
3. マージ操作において、2つの左傾ヒープを効率的に結合することができる。この操作では、二分木をマージする際にサブツリーの高さを考慮して、ヒープの形状を調整する必要がある。
4. 挿入操作も非常に効率的であり、通常の挿入操作と同じくらいの時間で行うことができる。

左傾ヒープは、ヒープのマージ操作が$O(\log n)$の時間で実行できるため、非常に効率的なデータ構造です。そのため、マージ操作が頻繁に発生するアプリケーションや、動的なデータの動的なソート、マージソートなどに適しています。

Rubyでの実装例

# frozen_string_literal: true

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(&block)
      @left&.each(&block)
      yield element
      @right&.each(&block)
    end
  end

  def initialize
    @root = nil
  end

  attr_reader :root

  def empty? = @root.nil?
  def make_empty = @root = nil

  def each(&block) = @root&.each(&block)
  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)$です。

斜めヒープの特徴は次のとおりです：

1. ヒープの形状が斜めに傾いているため、バランスを取るための回転操作が必要ありません。
2. マージ操作において、2つのヒープの根を比較し、小さい方を結合するだけで済みます。その後、再帰的にマージ操作を行うことで、新しいヒープが得られます。
3. 挿入操作も、新しい要素を単一のノードとしてヒープに追加し、その後にマージ操作を行うことで実現されます。

斜めヒープは、他のヒープデータ構造（例えば、二分ヒープや左傾ヒープ）と比較して、マージ操作が非常にシンプルであるため、実装が比較的簡単です。また、マージ操作の時間計算量が$O(\log n)$であるため、非常に効率的なデータ構造です。

Rubyでの実装例

# frozen_string_literal: true

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(&block)
      @left&.each(&block)
      yield key
      @right&.each(&block)
    end
  end

  def initialize
    @root = nil
  end

  attr_reader :root

  def each(&block) = @root&.each(&block)
  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

ヒープを使った高度なデータ構造

優先度付きキューの並行処理

優先度付きキューは、ヒープを使って実装することができます。並行処理環境では、複数のヒープを同時に処理することで、処理速度を向上させることができます。

マルチスレッド環境でのヒープの利用

マルチスレッド環境では、複数のスレッドが同時にヒープにアクセスする可能性があります。そのため、スレッドセーフなヒープを実装する必要があります。

その他の発展的なトピック

• フィボナッチヒープ
• ペアヒープ
• ソフトヒープ
• 動的ヒープ

まとめ

ヒープは、様々な応用拡張や高度なデータ構造に利用できる汎用性の高いデータ構造です。これらの発展的なトピックを理解することで、ヒープをより効果的に利用することができます。

ヒープの実装の高度なトピック

まとめと応用問題

外部リンク

• en:w:Heap (data structure)