Question

How does Heap Sort work?

Answer 1

1. Build Heap: Build a max-heap (for ascending order) or min-heap (for descending order) from the array.
2. Heapify: Repeatedly remove the root of the heap (which is the maximum or minimum element) and swap it with the last element in the array. After each removal, heapify the remaining heap.

Example Code in Python:

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left_child = 2 * i + 1
    right_child = 2 * i + 2

    # Check if left child exists and is greater than root
    if left_child < n and arr[left_child] > arr[largest]:
        largest = left_child

    # Check if right child exists and is greater than root
    if right_child < n and arr[right_child] > arr[largest]:
        largest = right_child

    # Swap the root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap
        heapify(arr, i, 0)

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)
 

This example demonstrates a max-heap and ascending order. For a min-heap and descending order, adjustments can be made accordingly.