Min Heap

py_ds.datastructures.heaps.MinHeap

MinHeap(items: Iterable[T] | None = None)

Bases: Heap

A min-heap implementation.

In a min-heap, the parent node is always less than or equal to its children. The root element is the minimum value in the heap.

Initialize the heap with optional items.

Parameters:

Name	Type	Description	Default
items	Iterable[T] | None	Optional iterable of items to initialize the heap with. If None, creates an empty heap.	None

Source code in src/py_ds/datastructures/heaps.py

def __init__(self, items: Iterable[T] | None = None):
    """Initialize the heap with optional items.

    Args:
        items: Optional iterable of items to initialize the heap with.
            If None, creates an empty heap.
    """
    items = items or []
    self._items: list[T] = []
    self._size: int = 0
    for item in items:
        self.push(item)

Functions

push

push(item: T) -> None

Add an item to the heap.

Parameters:

Name	Type	Description	Default
item	T	The item to add to the heap.	required

Time complexity: O(log n) where n is the number of elements.

Source code in src/py_ds/datastructures/heaps.py

def push(self, item: T) -> None:
    """Add an item to the heap.

    Args:
        item: The item to add to the heap.

    Time complexity: O(log n) where n is the number of elements.
    """
    index = self._size
    if index >= len(self._items):
        self._items.append(item)
    else:
        self._items[index] = item
    self._size += 1
    self._heapify_up()

pop

pop() -> T

Remove and return the root element of the heap.

Returns:

Type	Description
T	The root element of the heap (minimum for MinHeap, maximum for MaxHeap).

Raises:

Type	Description
IndexError	If the heap is empty.

Time complexity: O(log n) where n is the number of elements.

Source code in src/py_ds/datastructures/heaps.py

def pop(self) -> T:
    """Remove and return the root element of the heap.

    Returns:
        The root element of the heap (minimum for MinHeap, maximum for MaxHeap).

    Raises:
        IndexError: If the heap is empty.

    Time complexity: O(log n) where n is the number of elements.
    """
    if not self:
        raise IndexError('pop from an empty heap')
    item = self._items[0]
    self._items[0] = self._items[self._size - 1]
    self._size -= 1
    self._heapify_down()
    return item

peek

peek() -> T

Return the root element without removing it.

Returns:

Type	Description
T	The root element of the heap (minimum for MinHeap, maximum for MaxHeap).

Raises:

Type	Description
IndexError	If the heap is empty.

Time complexity: O(1).

Source code in src/py_ds/datastructures/heaps.py

def peek(self) -> T:
    """Return the root element without removing it.

    Returns:
        The root element of the heap (minimum for MinHeap, maximum for MaxHeap).

    Raises:
        IndexError: If the heap is empty.

    Time complexity: O(1).
    """
    if not self:
        raise IndexError('peek from an empty heap')
    return self._items[0]

__len__

__len__() -> int

Return the number of elements in the heap.

Returns:

Type	Description
int	The number of elements in the heap.

Time complexity: O(1).

Source code in src/py_ds/datastructures/heaps.py

def __len__(self) -> int:
    """Return the number of elements in the heap.

    Returns:
        The number of elements in the heap.

    Time complexity: O(1).
    """
    return self._size

__bool__

__bool__() -> bool

Return the truthiness of the heap.

Returns:

Type	Description
bool	False if the heap is empty, True otherwise.

Enables: if heap: ...

Source code in src/py_ds/datastructures/heaps.py

def __bool__(self) -> bool:
    """Return the truthiness of the heap.

    Returns:
        False if the heap is empty, True otherwise.

    Enables: `if heap: ...`
    """
    return self._size > 0