Heapify Algorithm

Heapify is the process of converting an unsorted array into a valid min-heap or max-heap in O(n) time. It ensures the structure and order properties of a heap are satisfied.

1. Heapify Overview

• Input: An unsorted array (e.g., [50, 80, 40, 20, 30, 90, 60, 10, 70]).
• Output: A valid heap (e.g., [ -, 10, 20, 40, 30, 80, 90, 60, 70, 50 ]).
• Key Idea: Start from the last non-leaf node and percolate down to restore the heap property.

2. Steps to Heapify

1. Identify Last Non-Leaf Node:
   • The last non-leaf node is at index n // 2 (where n is the number of elements).
   • Leaf nodes (indices n//2 + 1 to n) already satisfy the heap property.
2. Percolate Down:
   • For each node from the last non-leaf node to the root:
     • Compare the node with its children.
     • Swap with the smaller child (min-heap) or larger child (max-heap).
     • Repeat until the node is in the correct position.

3. Heapify Algorithm (Min-Heap)

Python Implementation

def heapify(arr):
    n = len(arr)
    # Start from the last non-leaf node and move upwards
    for i in range(n // 2, 0, -1):
        percolate_down(arr, i, n)

def percolate_down(arr, i, n):
    smallest = i  # Assume current node is the smallest
    left = 2 * i  # Left child index
    right = 2 * i + 1  # Right child index

    # Check if left child exists and is smaller than current node
    if left < n and arr[left] < arr[smallest]:
        smallest = left

    # Check if right child exists and is smaller than current node
    if right < n and arr[right] < arr[smallest]:
        smallest = right

    # If the smallest is not the current node, swap and continue percolating down
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        percolate_down(arr, smallest, n)  # Recur for the affected subtree

4. Example Walkthrough

Input Array: [50, 80, 40, 20, 30, 90, 60, 10, 70]

1. Add Dummy Element: Insert at index 0 for 1-based indexing.
   • Array: [ -, 50, 80, 40, 20, 30, 90, 60, 10, 70 ]
2. Heapify Process:
   • Start from the last non-leaf node (n//2 = 4):
     • Node 20 (index 4): Compare with children 10 and 70. Swap with 10.
     • Node 40 (index 3): Compare with children 90 and 60. No swap needed.
     • Node 80 (index 2): Compare with children 30 and 10. Swap with 10.
     • Node 50 (index 1): Compare with children 10 and 40. Swap with 10.