max heap Algorithm

The Max Heap algorithm is a specialized binary tree-based data structure that is widely used in numerous applications such as finding the maximum value in a dataset, sorting, and implementing priority queues. A Max Heap is essentially a complete binary tree with the unique property that the value of each parent node is greater than or equal to the values of its child nodes. This ensures that the highest value element is always present at the root of the tree. Max Heap allows for efficient search, insertion, and deletion operations, making it a highly versatile and powerful data structure. To perform the Max Heap algorithm, the elements of a dataset are first arranged into a binary tree, ensuring that the tree is complete, i.e., every level of the tree is filled except for possibly the last level, which is filled from left to right. The algorithm then iteratively compares each parent node with its children, and if a child node is found to be greater than the parent, the two nodes are swapped. This process, known as "heapifying," is repeated until the entire tree satisfies the Max Heap property. Insertion and deletion operations in a Max Heap involve updating the tree to maintain the Max Heap property after the operation. Overall, the Max Heap algorithm offers an elegant and efficient way to manage large datasets, providing valuable insights and quick access to the maximum value in the dataset.
class BinaryHeap:
    """
    A max-heap implementation in Python
    >>> binary_heap = BinaryHeap()
    >>> binary_heap.insert(6)
    >>> binary_heap.insert(10)
    >>> binary_heap.insert(15)
    >>> binary_heap.insert(12)
    >>> binary_heap.pop()
    15
    >>> binary_heap.pop()
    12
    >>> binary_heap.get_list
    [10, 6]
    >>> len(binary_heap)
    2
    """

    def __init__(self):
        self.__heap = [0]
        self.__size = 0

    def __swap_up(self, i: int) -> None:
        """ Swap the element up """
        temporary = self.__heap[i]
        while i // 2 > 0:
            if self.__heap[i] > self.__heap[i // 2]:
                self.__heap[i] = self.__heap[i // 2]
                self.__heap[i // 2] = temporary
            i //= 2

    def insert(self, value: int) -> None:
        """ Insert new element """
        self.__heap.append(value)
        self.__size += 1
        self.__swap_up(self.__size)

    def __swap_down(self, i: int) -> None:
        """ Swap the element down """
        while self.__size >= 2 * i:
            if 2 * i + 1 > self.__size:
                bigger_child = 2 * i
            else:
                if self.__heap[2 * i] > self.__heap[2 * i + 1]:
                    bigger_child = 2 * i
                else:
                    bigger_child = 2 * i + 1
            temporary = self.__heap[i]
            if self.__heap[i] < self.__heap[bigger_child]:
                self.__heap[i] = self.__heap[bigger_child]
                self.__heap[bigger_child] = temporary
            i = bigger_child

    def pop(self) -> int:
        """ Pop the root element """
        max_value = self.__heap[1]
        self.__heap[1] = self.__heap[self.__size]
        self.__size -= 1
        self.__heap.pop()
        self.__swap_down(1)
        return max_value

    @property
    def get_list(self):
        return self.__heap[1:]

    def __len__(self):
        """ Length of the array """
        return self.__size


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    # create an instance of BinaryHeap
    binary_heap = BinaryHeap()
    binary_heap.insert(6)
    binary_heap.insert(10)
    binary_heap.insert(15)
    binary_heap.insert(12)
    # pop root(max-values because it is max heap)
    print(binary_heap.pop())  # 15
    print(binary_heap.pop())  # 12
    # get the list and size after operations
    print(binary_heap.get_list)
    print(len(binary_heap))

LANGUAGE:

DARK MODE: