sorts.heap_sort

A pure Python implementation of the heap sort algorithm.

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

heap_sort(→ list[T])

A pure Python implementation of the heap sort algorithm.

heapify(→ None)

Module Contents

class sorts.heap_sort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...
__lt__(other: object, /) → bool
sorts.heap_sort.heap_sort[T: Comparable](unsorted: list[T]) → list[T]

A pure Python implementation of the heap sort algorithm.

Parameters:

unsorted – a mutable collection of comparable items

Returns:

the same collection ordered by ascending

Examples: >>> heap_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> heap_sort([]) [] >>> heap_sort([-2, -5, -45]) [-45, -5, -2] >>> heap_sort([3, 7, 9, 28, 123, -5, 8, -30, -200, 0, 4]) [-200, -30, -5, 0, 3, 4, 7, 8, 9, 28, 123] >>> heap_sort([“banana”, “apple”, “cherry”]) [‘apple’, ‘banana’, ‘cherry’] >>> heap_sort([3.14, 1.5, 2.7]) [1.5, 2.7, 3.14] >>> heap_sort([1, “two”]) # doctest: +ELLIPSIS Traceback (most recent call last): … TypeError: …

sorts.heap_sort.heapify[T: Comparable](unsorted: list[T], index: int, heap_size: int) → None
Parameters:

  • unsorted – unsorted list containing comparable items

  • index – index

  • heap_size – size of the heap

Returns:

None

>>> unsorted = [1, 4, 3, 5, 2]
>>> heapify(unsorted, 0, len(unsorted))
>>> unsorted
[4, 5, 3, 1, 2]
>>> heapify(unsorted, 0, len(unsorted))
>>> unsorted
[5, 4, 3, 1, 2]
sorts.heap_sort.user_input