pmAlg
def
The candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal elements of the prefix; a new element is compared with the candidates one by one. m is the number of elements still to scan.
Statement
open Finset in def pmAlg {n : ℕ} : ℕ → ℕ → List (Fin n) → PMTree n
- Defined in
- Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4, Theorem 11 (the candidate-set algorithm for the minimal elements); specialised to width 2
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 2
- Used by 5
- pm_alg_correctThe algorithm is correct on every width-2 poset.
- pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
- pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
open Finset in /-- The candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal elements of the prefix; a new element is compared with the candidates one by one. `m` is the number of elements still to scan. -/ def pmAlg {n : ℕ} : ℕ → ℕ → List (Fin n) → PMTree n := fun | 0, _, cs => PMTree.leaf cs.toFinset | m + 1, k, cs => if h : k < n then match cs with | [] => pmAlg m (k + 1) [⟨k, h⟩] | [t] => PMTree.node ⟨k, h⟩ t (fun r => match r with | PMAns.lt => pmAlg m (k + 1) [⟨k, h⟩] | PMAns.gt => pmAlg m (k + 1) [t] | PMAns.inc => pmAlg m (k + 1) [t, ⟨k, h⟩]) | [t1, t2] => PMTree.node ⟨k, h⟩ t1 (fun r => match r with | PMAns.gt => pmAlg m (k + 1) [t1, t2] | PMAns.lt => PMTree.node ⟨k, h⟩ t2 (fun r2 => match r2 with | PMAns.lt => pmAlg m (k + 1) [⟨k, h⟩] | PMAns.gt => pmAlg m (k + 1) [t1, t2] | PMAns.inc => pmAlg m (k + 1) [t2, ⟨k, h⟩]) | PMAns.inc => PMTree.node ⟨k, h⟩ t2 (fun r2 => match r2 with | PMAns.gt => pmAlg m (k + 1) [t1, t2] | PMAns.lt => pmAlg m (k + 1) [t1, ⟨k, h⟩] | PMAns.inc => pmAlg m (k + 1) [t1, t2])) | _ => PMTree.leaf ∅ else PMTree.leaf cs.toFinset