std.container.binaryheap

import std.algorithm.comparison : equal;
import std.range : take;
auto maxHeap = heapify([4, 7, 3, 1, 5]);
assert(maxHeap.take(3).equal([7, 5, 4]));

auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
assert(minHeap.take(3).equal([1, 3, 4]));

struct BinaryHeap(Store, alias less = "a < b") if (isRandomAccessRange!Store || isRandomAccessRange!(typeof(Store.init[])));

与えられたランダムアクセス可能な範囲型(通常はT[] )またはランダムアクセス可能なコンテナ型(通常はArray!T )の上にバイナリヒープコンテナを実装する。 のドキュメントでは、 BinaryHeap参照する基礎となる範囲または コンテナをヒープのストアと呼ぶ。

バイナリヒープは、その基盤となるストアに構造を付与し、 最大要素へのアクセス(front プロパティを使用)は Ο(1)の操作となり、その抽出(removeFront() メソッドを使用)はΟ(log n)の時間で高速に行われる。

less がデフォルトオプションである不等号演算子である場合、 BinaryHeapいわゆる最大ヒープを定義し、 最大の要素の抽出を最適化する。最小ヒープを定義するには、"a > b" をその述語としてBinaryHeapをインスタンス化する。

コンテナから要素を単に抽出する BinaryHeapコンテナから要素を抽出することは、Store の要素を遅延取得して降順で並べ替えることと同等である。 コンテナから要素を抽出して BinaryHeap完了まで 要素を抽出すると、基礎となるストアは昇順でソートされたままになるが、やはり 降順で要素が返される。

Store が範囲である場合、 BinaryHeapその範囲を超えることはできません。Store がinsertBack をサポートするコンテナである場合、 BinaryHeap要素をコンテナに追加することで、そのサイズを大きくすることができます。

containerコンテナ

Examples: 「Introduction to Algorithms」Cormen et al、p146からの例

「アルゴリズム入門」コーメン他著、p.146より

import std.algorithm.comparison : equal;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// 最大要素
writeln(h.front); // 16
// aはヒープ特性を持つ
assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));

xml-ph-0001@deepl.internalxml-ph-0001@deepl.internal

Examples: 標準入力範囲インターフェースを実装し、基礎となる範囲の降順での怠惰な反復処理を

BinaryHeap標準入力範囲インターフェースを実装し、 基礎となる範囲の降順での怠惰な反復処理を

import std.algorithm.comparison : equal;
import std.range : take;
int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
auto top5 = heapify(a).take(5);
assert(top5.equal([16, 14, 10, 9, 8]));

pp

this(Store s, size_t initialSize = size_t.max);

ストアを sヒープに変換する。 initialSize指定された場合、最初の initialSize要素のみが s less ヒープに変換され、その後、ヒープはr.length (Store が範囲の場合)または無限(Store がinsertBack を持つコンテナの場合)まで成長できる。min(r.length, initialSize) )の評価を実行する。

void acquire(Store s, size_t initialSize = size_t.max);

ストアの所有権を取得する。この操作の後、 sヒープが正しく動作しなくなる可能性がある。

void assume(Store s, size_t initialSize = size_t.max);

すでにヒープとして整理されていると仮定して、ストアの所有権を取得する。

auto release();

ヒープをクリアする。0 からlength までのストアの部分を返す。 これはヒープのプロパティを満たす。

@property bool empty();

ヒープが空の場合はtrue を、そうでない場合はfalse を返す。

@property BinaryHeap dup();

ヒープの複製を返す。この dupこのメソッドは、 基盤となるストアがサポートしている場合にのみ利用できる。

@property size_t length();

ヒープの長さを返す。

@property size_t capacity();

ヒープの容量を返す。これは、 基になるストアが範囲である場合はその長さ、基になるストアがコンテナである場合はその容量である。

@property ElementType!Store front();

ヒープの先頭部分のコピーを返す。これは、less によると、最大の要素である。

void clear();

ヒープを基底のストアから切り離すことで、ヒープをクリアする。

size_t insert(ElementType!Store value);

ストアに挿入する valueストアに挿入する。基礎となるストアが範囲であり、length == capacity の場合は、例外をスローする。

void removeFront();

alias popFront = removeFront;

ヒープから最大の要素を削除する。

ElementType!Store removeAny();

ヒープから最大の要素を削除し、そのコピーを返す。 要素は依然としてヒープのストア内に存在する。パフォーマンス上の 理由から、コピーにコストがかかるオブジェクトのヒープに対してremoveFront を使用したい場合がある。

void replaceFront(ElementType!Store value);

ストア内の最大要素を置き換える。 value。

bool conditionalInsert(ElementType!Store value);

ヒープに成長の余地がある場合は、 valueストアに挿入し、true を返す。 それ以外の場合、less(value, front) であれば、replaceFront(value) を呼び出し、再びtrue を返す。 それ以外の場合、 ヒープには影響を与えず、false を返す。 このメソッドは、 候補のセットの最小のk 要素を収集する必要がある シナリオで有用である。

bool conditionalSwap(ref ElementType!Store value);

ヒープが一杯の場合、入れ替えが許可される。less(value, front) の場合、 store.frontと"値"を交換し、true を返す。それ以外の場合、 ヒープには影響を与えず、false を返す。

xml-ph-0000@deepl.internalオブジェクトを返す便利な関数 初期化済み

BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s, size_t initialSize = size_t.max);

BinaryHeap!Store オブジェクトを返す便利な関数 で、 s。 initialSize。

objectobject

Examples:

import std.conv : to;
import std.range.primitives;
{
    // "アルゴリズム入門" コーメン他、p146より
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    auto h = heapify(a);
    h = heapify!"a < b"(a);
    writeln(h.front); // 16
    writeln(a); // [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
    auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
    for (; !h.empty; h.removeFront(), witness.popFront())
    {
        assert(!witness.empty);
        writeln(witness.front); // h.front
    }
    assert(witness.empty);
}
{
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    int[] b = new int[a.length];
    BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
    foreach (e; a)
    {
        h.insert(e);
    }
    writeln(b); // [16, 14, 10, 8, 7, 3, 9, 1, 4, 2]
}

objectobject

Examples: 直感に反する動作の例

直感に反する動作の例 ヒープがインスタンス化された後にストアを使用しないことが重要である。 少なくとも、ダイナミック配列の場合には。例えば、 ダイナミック配列をストアとして使用しているヒープに新しい要素を挿入すると、 ストアがすでに一杯になっている場合は、ストアの再割り当てが発生する。ヒープはもはや 元のダイナミック配列を指さず、新しいダイナミック配列を指す。

import std.stdio;
import std.algorithm.comparison : equal;
import std.container.binaryheap;

int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);

// バイナリーヒープツリーの内部表現
assert(a.equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));

h.replaceFront(30);
// 値16は30で置き換えられた
assert(a.equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));

// ストアへの変更はヒープに反映される
a[0] = 40;
writeln(h.front()); // 40

// 新しい要素を挿入すると、ストアが再割り当てされ、
// 元のストアは変更されない。
h.insert(20);
assert(a.equal([40, 14, 10, 8, 7, 9, 3, 2, 4, 1]));

// 元のストアに変更を加えても、ヒープには影響しない
a[0] = 60;
writeln(h.front()); // 40

dynamicDynamic