12.15 data.heap - ヒープ

Module: data.heap ¶

ヒープは最小値また最大値を効率よく取り出せるデータコンテナです。 <tree-map>は全てのエントリの順序を常に保っていますが (ツリーマップ参照)、 ヒープは最小値/最大値以外については部分的にしか順序を保持していません。 最小値/最大値が取り除かれる時点で内部を再構成して、次の最小値/最大値を見つけます。 したがって、最小値/最大値のみが必要な場合、treemapより効率が良いです。 さらに、バイナリヒープでは値をメモリ効率の良い詰められた形で保持できます。

Class: <binary-heap> ¶

{data.heap} バイナリヒープの実装です。内部的にmin-maxヒープを使っており、 最大値と最小値のどちらにもO(1)でアクセスできます。新たな値をpushしたり、 最大最小値をpopするのはO(log n)です。

バイナリヒープはまた、値をフラットなベクタに格納します。一般的なツリー構造が ノードあたりいくつかのポインタを必要とするのに比べずっとコンパクトです。 デフォルトでは疎なベクタ (疎なベクタ) がバッキングストレージとして使われ、 事実上上限なしでデータを格納できますが、通常のベクタやユニフォームベクタを バッキングストレージとして指定することもできます。

バイナリヒープはスレッドセーフではありません。複数のスレッドでアクセスする 可能性がある場合は、atomに入れるか、mutexを適切に使ってください(同期プリミティブ参照)。

Function: make-binary-heap :key comparator storage key ¶

{data.heap} 新しいバイナリヒープを作って返します。

comparatorキーワード引数は、エントリの比較方法を指定する比較器です。 比較手続きを持っていなければなりません。省略時はdefault-comparatorが 使われます。比較器について詳しくは基本的な比較器を参照してください。

storageキーワード引数には、データの格納に使うデータ構造を渡します。引数は ベクタ、ユニフォームベクタ、あるいは疎ベクタ(疎なベクタ参照)の インスタンスでなければなりません。省略時は<sparse-vector>の インスタンスが使われます。

ベクタまたはユニフォームベクタを渡した場合、そのベクタの大きさが ヒープが格納できる要素の最大数を決めます。 それが一杯になった時に自動的に拡張されることはありません。

keyキーワード引数は手続きでなければならず、要素の比較の前に各要素に適用されます。 この手続きを使って、実際に比較される値に付随するデータを格納しておくことができます。 次の例では、データのcarを使って比較しています。

(define *heap* (make-binary-heap :key car))
(binary-heap-push! *heap* (cons 1 'a))
(binary-heap-push! *heap* (cons 3 'b))
(binary-heap-push! *heap* (cons 1 'c))

(binary-heap-find-min *heap*) ⇒ (1 . c)
(binary-heap-find-max *heap*) ⇒ (3 . b)

Function: build-binary-heap storage :key comparator key num-entries ¶

{data.heap} storageに入っているデータを使ってヒープを作り返します。 (この操作はしばしばヒープ化(heapify)と呼ばれます。) データ格納場所を新たにアロケートせずにヒープを作ることが可能です。 comparatorおよびkey引数はmake-binary-heapと同じです。

storageはベクタ、ユニフォームベクタ、疎ベクタのインスタンスでなければ なりません。このデータはヒープの属性を満たすために変更され、さらには 作られたヒープのデータ格納場所となります。ヒープの一部になるので、 storageを後から変更してはなりません。

storageの要素のうち、先頭からnum-entriesまでの要素が 有効であるとしてヒープ化されます。num-entriesが省略されるか #fであれば、ベクタおよびユニフォームベクタはその全てが、 疎ベクタはsparse-vector-num-entriesまでの要素がヒープ化されます。

Function: binary-heap-copy heap ¶

{data.heap} ヒープをコピーして返します。データ格納場所も全てコピーされます。

Function: binary-heap-clear! heap ¶

{data.heap} ヒープを空にします。

Function: binary-heap-num-entries heap ¶

{data.heap} ヒープ中の要素数を返します。

Function: binary-heap-empty? heap ¶

{data.heap} ヒープが空なら#tを、そうでなければ#fを返します。

Function: binary-heap-push! heap item ¶

{data.heap} itemをheapに挿入します。O(log n)の操作です。 ヒープが既に一杯であった場合はエラーが通知されます。

Function: binary-heap-find-min heap :optional fallback ¶

Function: binary-heap-find-max heap :optional fallback ¶

{data.heap} それぞれヒープ中の最小および最大の要素を返します。O(1)の操作です。 ヒープ自体は変更されません。

ヒープが空の場合、fallbackが与えられればそれが返され、 そうでなければエラーが通知されます。

Function: binary-heap-pop-min! heap ¶

Function: binary-heap-pop-max! heap ¶

{data.heap} それぞれヒープから最小および最大の要素を取り除き、取り除いた要素を返します。 O(log n)の操作です。 ヒープが空ならエラーが通知されます。

以下の手続きは一般的なデータ構造としてのヒープの操作には含まれませんが、 便利なので用意してあります。

Function: binary-heap-swap-min! heap item ¶

Function: binary-heap-swap-max! heap item ¶

{data.heap} これらはそれぞれ以下のコードと操作的には等価です。

(begin0 (binary-heap-pop-min! heap)
  (binary-heap-push! heap item))

(begin0 (binary-heap-pop-max! heap)
  (binary-heap-push! heap item))

ただしこれらの手続きは、 ヒープ特性を維持するための手続きを呼び出し毎に1回しか行わないので、 やや効率的です。

Function: binary-heap-find pred heap :optional failure ¶

{data.heap} ヒープの中で、述語predを満たす要素を返します。predを満たす要素が 複数ある場合にどれが返るかは不定です。predを満たす要素が無ければ サンクfailureが呼ばれます。failureのデフォルトは (^[] #f)です、O(n)の操作です。

註: 0.9.10まで、引数の順序は(binary-heap-find heap pred)でしたが、 他の *-find 系インタフェースと合わせるために変更されました。 互換性のため、古いインタフェースで呼び出しても動作するようになっていますが、 新たに書くコードは新しいインタフェースを使ってください。

Function: binary-heap-remove! heap pred ¶

{data.heap} predを満たす要素を全てヒープから取り除きます。O(n)の操作です。

Function: binary-heap-delete! heap item ¶

{data.heap} itemに等しい要素を全てヒープから取り除きます。「等しい」の判定には ヒープの比較器およびキー手続きが使われます。O(n)の操作です。

キー手続きは、比較の前にitemにも適用されます。