Heap construction by insertion in Python
Building a heap by inserting elements one at a time, which takes O(n log n) time in the worst case, slower than bottom-up construction.
- File
heap_construction_by_insertion.py, 30 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/heap-construction-by-insertion/. The authors are listed in prov/0PQJ7X.jsonl.
from typing import Any, Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: Any, /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def sift_up(a: list[T], j: int) -> None:
"""Move a[j] up in the max-heap a[0:j+1]; a[0:j] must be a max-heap."""
i = j # @line L2
while i > 0 and a[(i - 1) // 2] < a[i]: # @line L3
p = (i - 1) // 2
a[i], a[p] = a[p], a[i] # @line L4
i = p # @line L5
def heap_construction_by_insertion(a: list[T]) -> None:
"""Rearrange a in place into a max-heap by inserting a[1], a[2], ... in turn.
O(n log n) time in the worst case, O(n) expected time on a random order,
O(1) extra space. After step j, a[0:j+1] is a max-heap.
"""
for j in range(1, len(a)): # @line L1
sift_up(a, j)
test_heap_construction_by_insertion.py 74 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/heap-construction-by-insertion/. The authors are listed in prov/0PQJ7X.jsonl.
import itertools
import random
from collections import Counter
from heap_construction_by_insertion import heap_construction_by_insertion, sift_up
class C:
count = 0
def __init__(self, v: int) -> None:
self.v = v
def __lt__(self, other: "C") -> bool:
C.count += 1
return self.v < other.v
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_clrs_input() -> None:
a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_construction_by_insertion(a)
assert a == [16, 14, 10, 8, 7, 3, 9, 1, 4, 2]
C.count = 0
b = [C(v) for v in [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]]
heap_construction_by_insertion(b)
assert C.count == 17
def test_prefix_is_heap() -> None:
a = [3, 9, 2, 7, 7, 8, 1, 10]
for j in range(1, len(a)):
sift_up(a, j)
assert is_max_heap(a[: j + 1])
def test_worst_case_count() -> None:
for n in range(1, 200):
C.count = 0
b = [C(v) for v in range(n)]
heap_construction_by_insertion(b)
assert C.count == sum(j.bit_length() - 1 for j in range(1, n + 1))
assert b[0].v == n - 1
def test_edges() -> None:
for a in ([], [1], [1, 1, 1], [2, 1], [1, 2]):
b = list(a)
heap_construction_by_insertion(b)
assert is_max_heap(b) and sorted(b) == sorted(a)
def test_all_permutations_small() -> None:
for n in range(8):
for p in itertools.permutations(range(n)):
b = list(p)
heap_construction_by_insertion(b)
assert is_max_heap(b) and sorted(b) == list(range(n))
def test_random() -> None:
rng = random.Random(1991)
for _ in range(600):
a = [rng.randint(-20, 20) for _ in range(rng.randint(0, 60))]
b = list(a)
heap_construction_by_insertion(b)
assert is_max_heap(b)
assert Counter(b) == Counter(a)
What the next level needs
- the tests did not run in this build