Heaps

A heap is a specialized binary tree-based data structure that satisfies the heap property. It can be one of two types:

• Min-Heap: The value at each node is less than or equal to the values of its children.
• Max-Heap: The value at each node is greater than or equal to the values of its children.

This property makes heaps particularly useful for efficient minimum or maximum extraction.

Properties of Heaps:

1. A heap is a complete binary tree, meaning every level except possibly the last is filled, and all nodes are as left-leaning as possible.
2. The root node is the minimum (in a min-heap) or maximum (in a max-heap) value.
3. Heaps are often represented using arrays, which allow easy access to parent and child nodes via index calculations.

Min-Heap and Max-Heap

• Min-Heap: In a min-heap, the smallest element is at the root. Each parent node has a value less than or equal to its children, which ensures that removing the root will yield the smallest element.
• Max-Heap: In a max-heap, the largest element is at the root. Each parent node has a value greater than or equal to its children, which ensures that removing the root will yield the largest element.

Array Representation:

For an element at index i in a zero-based index array:

• Left Child: 2*i + 1
• Right Child: 2*i + 2
• Parent: (i - 1) // 2

Heapify Operation

The heapify operation is used to maintain the heap property, either in a top-down or bottom-up approach.

There are two types of heapify operations: 1. Up-Heapify (Bubble-Up): Used when a new element is added to the heap. 2. Down-Heapify (Sink-Down): Used to restore the heap after removing the root element.

Let’s look at the down-heapify operation (often just called heapify) used to maintain the heap property in a subtree rooted at a given index.

Example: Min-Heapify and Max-Heapify

We’ll implement both min-heapify and max-heapify operations. Here, we’ll focus on the down-heapify operation, commonly used when deleting the root element.

from typing import List

def min_heapify(arr: List[int], n: int, i: int) -> None:
    """
    Min-heapify operation on a subtree rooted at index i.
    - arr: list representing the heap
    - n: total number of elements in the heap
    - i: index of the root node of the subtree
    """
    smallest = i         # Initialize smallest as root
    left = 2 * i + 1     # Left child index
    right = 2 * i + 2    # Right child index
    
    # If left child is smaller than root
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    # If right child is smaller than smallest so far
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    # If smallest is not root, swap and continue heapifying
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]  # Swap
        min_heapify(arr, n, smallest)                  # Recursively heapify the affected subtree

def max_heapify(arr: List[int], n: int, i: int) -> None:
    """
    Max-heapify operation on a subtree rooted at index i.
    - arr: list representing the heap
    - n: total number of elements in the heap
    - i: index of the root node of the subtree
    """
    largest = i         # Initialize largest as root
    left = 2 * i + 1    # Left child index
    right = 2 * i + 2   # Right child index
    
    # If left child is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # If right child is greater than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # If largest is not root, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        max_heapify(arr, n, largest)                 # Recursively heapify the affected subtree

Explanation of the Code

Function Parameters:

• arr: The list representing the heap.
• n: The size of the heap (useful for heapifying only a part of the array).
• i: The index of the current node being heapified.

Process:

• We first set the smallest or largest to the index i.
• We check both the left and right children:
• For min-heapify, we find the smallest among the current node and its children.
• For max-heapify, we find the largest among the current node and its children.
• If either child is smaller (or larger), we swap it with the current node and recursively call heapify on the affected subtree.

Common Mistakes

Off-By-One Errors:

• Using incorrect indices for left and right children can lead to errors, especially in languages with zero-based indexing.
• Always ensure left and right indices are within bounds before accessing arr[left] and arr[right].

Not Swapping Correctly:

• Forgetting to update the smallest or largest when a child is smaller or larger can lead to an infinite loop or incorrect heap structures.

Confusing Min and Max Heaps:

• Beginners often confuse the conditions for min-heap and max-heap. Make sure you’re comparing correctly (use < for min-heap and > for max-heap).