Floyd's heap construction in Python
Sifts down every internal node from the last to the first, building a heap in O(n) time.
- File
floyd_heap_construction.py, 35 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/floyd-heap-construction/. The authors are listed in prov/ADHNWH.jsonl.
from typing import Any, Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: Any, /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def max_heapify(a: list[T], n: int, i: int) -> None:
"""Sift a[i] down in the max-heap a[0:n]. The subtrees of the children of i must be max-heaps."""
while True: # @line L3
left, right, m = 2 * i + 1, 2 * i + 2, i # @line L4
if left < n and a[m] < a[left]: # @line L5
m = left
if right < n and a[m] < a[right]: # @line L6
m = right
if m == i: # @line L7
return
a[i], a[m] = a[m], a[i] # @line L8
i = m # @line L9
def floyd_heap_construction(a: list[T]) -> None:
"""Rearrange a in place into a max-heap: a[(j - 1) // 2] >= a[j] for each j >= 1.
Runs in O(n) time with fewer than 2n comparisons and O(1) extra space.
"""
n = len(a)
for i in range(n // 2 - 1, -1, -1): # @line L1
max_heapify(a, n, i) # @line L2
test_floyd_heap_construction.py 54 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/floyd-heap-construction/. The authors are listed in prov/ADHNWH.jsonl.
import itertools
import random
from floyd_heap_construction import floyd_heap_construction, max_heapify
def is_max_heap(a: list[int]) -> bool:
return all(a[(j - 1) // 2] >= a[j] for j in range(1, len(a)))
def test_example() -> None:
a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
floyd_heap_construction(a)
assert a == [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
def test_edges() -> None:
for a in ([], [1], [1, 2], [2, 1], [5, 5, 5, 5], [1, 2, 3, 4], list(range(20))):
b = list(a)
floyd_heap_construction(b)
assert is_max_heap(b)
assert sorted(b) == sorted(a)
def test_wrong_order_pitfall() -> None:
a = [1, 2, 3, 4]
n = len(a)
for i in range(0, n // 2):
max_heapify(a, n, i)
assert a == [3, 4, 1, 2] and not is_max_heap(a)
b = [1, 2, 3, 4]
floyd_heap_construction(b)
assert is_max_heap(b)
def test_all_permutations() -> None:
for n in range(8):
for p in itertools.permutations(range(n)):
b = list(p)
floyd_heap_construction(b)
assert is_max_heap(b) and sorted(b) == list(range(n))
def test_random_against_sorted() -> None:
rng = random.Random(1964)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 70))]
b = list(a)
floyd_heap_construction(b)
assert is_max_heap(b)
assert sorted(b) == sorted(a)
What the next level needs
- the tests did not run in this build