Weak heapsort in Python
Heapsort variant using weak heaps, needing at most n log n + 0.1n comparisons.
- File
weak_heapsort.py, 46 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/weak-heapsort/. The authors are listed in prov/KTRHK1.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def d_ancestor(r: list[int], j: int) -> int:
"""Return the distinguished ancestor of node j > 0."""
while (j & 1) == r[j >> 1]: # j is a left child: go up
j >>= 1
return j >> 1
def join(a: list[T], r: list[int], i: int, j: int) -> int:
"""Make i the larger of a[i] and a[j]; i is the d-ancestor of j. Returns 1 comparison."""
if a[i] < a[j]:
a[i], a[j] = a[j], a[i]
r[j] ^= 1 # swap the two subtrees of j
return 1
def weak_heapsort(a: list[T]) -> int:
"""Sort a in place. Return the number of comparisons."""
n = len(a)
r = [0] * n # @line L1
c = 0
for j in range(n - 1, 0, -1): # @line L2
c += join(a, r, d_ancestor(r, j), j) # @line L3
for m in range(n - 1, 1, -1): # @line L4
a[0], a[m] = a[m], a[0] # @line L5
x = 1 # @line L6
while 2 * x + r[x] < m:
x = 2 * x + r[x]
while x > 0: # @line L7
c += join(a, r, 0, x) # @line L8
x >>= 1
if n >= 2:
a[0], a[1] = a[1], a[0] # @line L9
return c
test_weak_heapsort.py 47 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/weak-heapsort/. The authors are listed in prov/KTRHK1.jsonl.
import itertools
import math
import random
from weak_heapsort import weak_heapsort
def worst(n: int) -> int:
k = math.ceil(math.log2(n))
return n * k - 2**k + n - k
def test_example() -> None:
a = [5, 1, 4, 2, 8, 3, 7, 6]
assert weak_heapsort(a) == 19
assert a == [1, 2, 3, 4, 5, 6, 7, 8]
def test_all_small_permutations() -> None:
for n in range(2, 8):
most = 0
for p in itertools.permutations(range(n)):
a = list(p)
most = max(most, weak_heapsort(a))
assert a == list(range(n))
assert most == worst(n)
def test_bound_on_random_input() -> None:
rng = random.Random(3)
for n in (9, 100, 1000, 1500):
a = [rng.randrange(n) for _ in range(n)]
b = sorted(a)
c = weak_heapsort(a)
assert a == b
assert c <= worst(n)
assert c <= n * math.log2(n) + 0.087 * n
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [1, 2, 3]):
b = list(a)
weak_heapsort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build