data_structures.heap.heap

Attributes

T

heap

Classes

Comparable

Base class for protocol classes.

Heap

A Max Heap Implementation

Module Contents

class data_structures.heap.heap.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:
        ...
abstractmethod __eq__(other: object) → bool
abstractmethod __gt__(other: T) → bool
abstractmethod __lt__(other: T) → bool
class data_structures.heap.heap.Heap

A Max Heap Implementation

>>> unsorted = [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5]
>>> h = Heap()
>>> h.build_max_heap(unsorted)
>>> h
[209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5]
>>>
>>> h.extract_max()
209
>>> h
[201, 107, 25, 103, 11, 15, 1, 9, 7, 5]
>>>
>>> h.insert(100)
>>> h
[201, 107, 25, 103, 100, 15, 1, 9, 7, 5, 11]
>>>
>>> h.heap_sort()
>>> h
[1, 5, 7, 9, 11, 15, 25, 100, 103, 107, 201]
__repr__() → str
build_max_heap(collection: collections.abc.Iterable[T]) → None

build max heap from an unsorted array

>>> h = Heap()
>>> h.build_max_heap([20,40,50,20,10])
>>> h
[50, 40, 20, 20, 10]

>>> h = Heap()
>>> h.build_max_heap([1,2,3,4,5,6,7,8,9,0])
>>> h
[9, 8, 7, 4, 5, 6, 3, 2, 1, 0]

>>> h = Heap()
>>> h.build_max_heap([514,5,61,57,8,99,105])
>>> h
[514, 57, 105, 5, 8, 99, 61]

>>> h = Heap()
>>> h.build_max_heap([514,5,61.6,57,8,9.9,105])
>>> h
[514, 57, 105, 5, 8, 9.9, 61.6]
extract_max() → T

get and remove max from heap

>>> h = Heap()
>>> h.build_max_heap([20,40,50,20,10])
>>> h.extract_max()
50

>>> h = Heap()
>>> h.build_max_heap([514,5,61,57,8,99,105])
>>> h.extract_max()
514

>>> h = Heap()
>>> h.build_max_heap([1,2,3,4,5,6,7,8,9,0])
>>> h.extract_max()
9
heap_sort() → None
insert(value: T) → None

insert a new value into the max heap

>>> h = Heap()
>>> h.insert(10)
>>> h
[10]

>>> h = Heap()
>>> h.insert(10)
>>> h.insert(10)
>>> h
[10, 10]

>>> h = Heap()
>>> h.insert(10)
>>> h.insert(10.1)
>>> h
[10.1, 10]

>>> h = Heap()
>>> h.insert(0.1)
>>> h.insert(0)
>>> h.insert(9)
>>> h.insert(5)
>>> h
[9, 5, 0.1, 0]
left_child_idx(parent_idx: int) → int | None

return the left child index if the left child exists. if not, return None.

max_heapify(index: int) → None

correct a single violation of the heap property in a subtree’s root.

It is the function that is responsible for restoring the property of Max heap i.e the maximum element is always at top.

parent_index(child_idx: int) → int | None

returns the parent index based on the given child index

>>> h = Heap()
>>> h.build_max_heap([103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5])
>>> h
[209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5]

>>> h.parent_index(-1)  # returns none if index is <=0

>>> h.parent_index(0)   # returns none if index is <=0

>>> h.parent_index(1)
0
>>> h.parent_index(2)
0
>>> h.parent_index(3)
1
>>> h.parent_index(4)
1
>>> h.parent_index(5)
2
>>> h.parent_index(10.5)
4.0
>>> h.parent_index(209.0)
104.0
>>> h.parent_index("Test")
Traceback (most recent call last):
...
TypeError: '>' not supported between instances of 'str' and 'int'
right_child_idx(parent_idx: int) → int | None

return the right child index if the right child exists. if not, return None.

h: list[T] = []
heap_size: int = 0
data_structures.heap.heap.T
data_structures.heap.heap.heap: Heap[int]