heap・ordered setで全候補の極値を保つ

概要

比較可能な候補全体から極値・順位・隣接を繰り返し取り出すため、動的な順序を保つ。

考え方

最小候補だけ欲しいならheap、大小順の前後や区間を扱うならordered setを選ぶ。どちらも「候補を保存する」構造だが、効率よく答えられるqueryが違う。

成立条件と計算量

二分heapのpush/popはO(log N)、最小参照O(1)。平衡探索木の挿入・削除・lower_boundはO(log N)。heapで任意削除するならID索引や遅延削除の不変量が必要になる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。極値の取得と近傍の検索を区別し、heapとordered setを使い分ける入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-ordered-set-heap

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 支配関係で一度捨てた候補を戻さない単調stack・queue。

根拠