二分ヒープをPHPで手軽に扱う

優先度付きキューと二分ヒープ

AtCoderのABC第141回のD問題はmaxヒープを使うことで簡単に回答できます。

優先度付きキュー（priority queue）とは、各要素に優先度をつけて、優先度の高いものから順番に要素を取り出すという抽象データ型です。

優先度付きキューの実装方法の1つに、二分ヒープ（Binary Heap）というデータ構造があります。

二分ヒープでは、要素の挿入・削除はO(log n)で、先頭のノードの値の取得はO(1)で行うことができます。

maxヒープを使うと、計算量O(1)で最大値を取り出すことができるんです。

しかもPHPでは、このmaxヒープをライブラリを使うことなく手軽に使うことができます。

「SplMaxHeap」はPHPで手軽にmaxヒープを扱うためのクラス

PHPではmaxヒープを利用するためのSplMaxHeapというクラスがあります。

使い方を見てみましょう。

<?php

$numbers = [2, 5, 9, 4, 6];

// ①SplMaxHeapクラスのオブジェクトを生成しています
$heap = new SplMaxHeap();

foreach ($numbers as $n) {
    // ②値を$heapに格納していきます
    $heap->insert($n);
}

// ③heapにノードがあるかを調べ、ある場合はtrue、ない場合はfalseを返します
while($heap->valid()) {
    // ④ heapの先頭からノードを取り出します
    echo $heap->extract() . ' ';
}

// 出力
// 9 6 5 4 2

以上が基本的な使い方です。

また、先頭のノードを常に最小値にするminヒープを使う場合は、SplMinHeapを使います。

PHPにはSplPriorityQueueクラスもあります。

ただ、値をinsertする際に、実装者は値の優先度を決める必要があります。

Python, Rustでもmaxヒープを簡単に扱える

Pythonではheapq、Rustではstd::collections::BinaryHeapを使って手軽にmaxヒープを扱うことができます。

各プログラミング言語では複雑なアルゴリズムを手軽に扱うことができるように、便利なクラスやモジュールが実装されているんですね。

だいぶ知ったつもりでいましたが、まだまだPHPも掘り甲斐があると思いました。

プログラミングコンテストのチャレンジから得た学びでした。