heapBlockSwap
The top-level transposition swap between block j and block j + 1 in the order-(n + 1) Heap algorithm, which for j < n swaps the trailing element Fin.last n with 0 if n + 1 is odd and with j if n + 1 is even, and is the identity otherwise.
Statement
def heapBlockSwap (n : ℕ) (j : ℕ) : Equiv.Perm (Fin (n + 1))- Defined in
- arXiv:2611.05397 Definition 5
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Used by 1
- heapBlockBaseThe block base permutation for the q-th block of the order-(n + 1) Heap algorithm, defined recursively with the 0-th block base as the…
Read back from the Lean
Given natural numbers n and j, heapBlockSwap n j is defined as a permutation of Fin (n + 1) (Equiv.Perm (Fin (n + 1))):
- If j < n:
- If (n + 1) % 2 = 1 (i.e., n + 1 is odd), it is the transposition swapping 0 : Fin (n + 1) and Fin.last n (index n).
- Otherwise (i.e., n + 1 is even), it is the transposition swapping j : Fin (n + 1) and Fin.last n (index n).
- If ¬(j < n) (i.e., j ≥ n), it is the identity permutation 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The top-level transposition swap between adjacent blocks in the order-(n + 1) Heap algorithm. -/ def heapBlockSwap (n : ℕ) (j : ℕ) : Equiv.Perm (Fin (n + 1)) := if hj : j < n then if (n + 1) % 2 = 1 then Equiv.swap ⟨0, by omega⟩ (Fin.last n) else Equiv.swap ⟨j, by omega⟩ (Fin.last n) else 1