🐷

【C#データ構造】優先度付き待ち行列とは？ヒープとは？

2024/06/28に公開

 はじめに今回は応用的なデータ構造について解説します。

基本的なデータ構造は以下で解説しています。

https://zenn.dev/student_blog/articles/a61789dbbca794
本記事では、C#のコード例を交えて、具体的な実装方法についても説明します。

 優先度付き待ち行列優先度付き待ち行列（Priority Queue）は、各要素に優先度を持たせるデータ構造です。通常の待ち行列とは異なり、先に入った要素が必ずしも先に出るわけではなく、優先度が高い要素が優先的に取り出されます。

 主な用途
タスクスケジューリング：CPUスケジューリングで、優先度の高いタスクを先に実行します。

グラフアルゴリズム：最短経路アルゴリズムなどで使用されます。

シミュレーションシステム：イベント駆動型シミュレーションで、イベントを優先度順に処理します。

 ヒープヒープは、半順序のついた2分木と呼ばれるデータ構造です。親ノードは最後尾を除いて必ず2つの子ノードを持ちます。また、ヒープには最大ヒープと最小ヒープの2種類があります。最大ヒープでは、親ノードの値が子ノードの値よりも常に大きく、最小ヒープでは親ノードの値が子ノードの値よりも常に小さいという特性を持ちます。

 優先度付き待ち行列との違い優先度付き待ち行列であれば最小値を取り出す，要素を挿入するという操作ともに全体を探索しなければならないのでO(n)の手間がかかります。ヒープの場合はO(log(2) n)で済ませることが可能になります。

 主な用途
優先度付き待ち行列の実装：ヒープは優先度付き待ち行列の効率的な実装に使用されます。

 ヒープへの挿入ヒープに要素を挿入する際には、次の手順を踏みます：

末尾に追加: ヒープの完全二分木の性質を維持するため、まず新しい要素を木の末尾に追加します。

上に浮かせる (Bubble Up): 新しく追加した要素を親ノードと比較し、ヒープ特性を維持するために必要に応じて親ノードと交換します。この操作を、適切な位置に収まるまで繰り返します。

 挿入の具体例例えば、要素5を以下のヒープに挿入するとします：
        3
       / \
      6   8
     / \
    7   9

末尾に追加:
        3
       / \
      6   8
     / \  /
    7   9 5

上に浮かせる:

5とその親ノード8を比較し、5 < 8なので交換します。

        3
       / \
      6   5
     / \  /
    7   9 8
5 > 3であるためこれ以上上に浮かせません。

これで挿入が完了しました。

 ヒープからの削除ヒープから要素を削除する際には、通常は最小 (最小ヒープの場合) もしくは最大 (最大ヒープの場合) の要素を削除します。以下は最小ヒープでの削除の手順です：

ルートの削除: ヒープの根ノード (最小要素) を削除します。

末尾要素を根に移動: ヒープの完全二分木の性質を維持するため、木の末尾にある要素を根に移動します。

下に沈める (Bubble Down): 新しい根ノードを子ノードと比較し、ヒープ特性を維持するために必要に応じて子ノードと交換します。この操作を、適切な位置に収まるまで繰り返します。

 削除の具体例例えば、以下のヒープから最小要素3を削除するとします：
        3
       / \
      6   5
     / \  /
    7   9 8

ルートの削除:
        X
       / \
      6   5
     / \  /
    7   9 8

末尾要素を根に移動:
        8
       / \
      6   5
     / \
    7   9

下に沈める:

8とその子ノード6、5を比較し、5 < 6であるため子ノードの最小値は5です．さらに，8 > 5なので5と交換します。

        5
       / \
      6   8
     / \
    7   9
子ノードがなくなったのでこれで削除が完了しました。

もし、子ノードがあれば同様に比較する必要があります。

 ヒープの実装方法C#での最大ヒープの実装例を示します。以下のコードでは、最小ヒープの基本的な操作（挿入と削除）を実装しています。
using System;
using System.Collections.Generic;
using System.Threading;

/// <summary>
/// 最小ヒープを実装しているクラスです．
/// 最小ヒープとは親が子より小さい値を常に持ちます．
/// </summary>
/// <typeparam name="T"></typeparam>
public class Heap<T> where T : IComparable<T>
{
  private List<T> data;

  public Heap()
  {
    data = new List<T>();
  }

  /// <summary>
  /// 要素の挿入を行う．
  /// </summary>
  /// <param name="_item"></param>
  public void Insert(T _item)
  {
    data.Add(_item);
    int _child = data.Count - 1;//最初は末尾ノードに追加予定

    //挿入場所が決定されるまで続ける．
    while (_child > 0)
    {
      int _parent = (_child - 1) / 2;//親ノード

      //親ノードの方が値が小さいならば今以上に上に浮かせることは出来ない
      if (data[_child].CompareTo(data[_parent]) >= 0)
      {
        break;
      }

      //親ノードと子ノードの入替を行う
      T _temp = data[_child];
      data[_child] = data[_parent];
      data[_parent] = _temp;

      _child = _parent;
    }
  }

  public int Count { get { return data.Count; } }

  /// <summary>
  /// 最小値の削除を行う．
  /// </summary>
  /// <returns></returns>
  /// <exception cref="InvalidOperationException"></exception>
  public T DeleteMin()
  {
    if (data.Count == 0) throw new InvalidOperationException("The heap is empty");

    //最小値を取り除き，末尾ノードを根ノードに．
    T _min = data[0];
    data[0] = data[data.Count - 1];
    data.RemoveAt(data.Count - 1);

    int _parent = 0;

    while (2 * _parent + 1 <= data.Count - 1)
    {
      //子ノードのうち最小値を求める
      int _leftChild = 2 * _parent + 1;//親から見た左子ノード
      int _rightChild = 2 * _parent + 2;//親から見た右子ノード
      int _minChild = _leftChild;
      if (_rightChild <= data.Count - 1 && data[_leftChild].CompareTo(data[_rightChild]) > 0)
      {
        _minChild = _rightChild;
      }

      //子ノードと比較する
      if (data[_minChild].CompareTo(data[_parent]) < 0)
      {
        //親ノードの方が値が大きいなら親ノードと子ノードの入替を行う
        T _temp = data[_minChild];
        data[_minChild] = data[_parent];
        data[_parent] = _temp;

        _parent = _minChild;
      }
      else break;
    }
    return _min;
  }
}

public class Example
{
  public static void Main()
  {
    Heap<int> _heap = new Heap<int>();
    _heap.Insert(31);
    _heap.Insert(21);
    _heap.Insert(48);
    _heap.Insert(9);
    _heap.DeleteMin();
    _heap.Insert(26);
    _heap.Insert(13);
    _heap.DeleteMin();

    while (_heap.Count > 0)
    {
      Console.WriteLine(_heap.DeleteMin());
    }
  }
}
このコードを実行すると、ヒープに挿入された要素が最小値から順に取り出されることが確認できます。

 計算量木の高さをk,要素数をnとすると，
 
2^{k-1} \leqq n
の関係になるため

k \leqq 1 + log2(n)
となり全体の計算量は

O(log2(n))
となる。

 参考書籍データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)

https://amzn.to/3YtOnpz

はじめに

優先度付き待ち行列

主な用途

ヒープ

優先度付き待ち行列との違い

主な用途

ヒープへの挿入

挿入の具体例

ヒープからの削除

削除の具体例

ヒープの実装方法

計算量

参考書籍

Discussion