Overview

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It consists of two main phases:

1. Building a max heap from the input data.
2. Repeatedly extracting the maximum element from the heap and rebuilding the heap until all elements are sorted.

Python Implementation

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index

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

    # Check if right child exists and is greater than largest so far
    if right < n and arr[largest] < arr[right]:
        largest = right

    # If largest is not root, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        heapify(arr, n, largest)

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

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

    # One by one extract elements from heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)

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

Program Structure

The program consists of two main functions: heapify and heap_sort. Here’s a breakdown of their functionality:

1. heapify(arr, n, i)

• Parameters:
  • arr: The array to be sorted.
  • n: The size of the heap.
  • i: The index of the element to heapify.
• Purpose: Ensures that the subtree rooted at index i is a max heap. It compares the parent node with its children and swaps elements as necessary.

2. heap_sort(arr)

• Parameters:
  • arr: The array to be sorted.
• Purpose:
  • Builds a max heap from the input array.
  • Extracts the maximum element one by one from the heap and places it at the end of the array.

Example Usage

The provided example demonstrates how to use the heap_sort function. The original array is printed before sorting, and the sorted array is displayed after the algorithm has been executed.

Conclusion

Heap sort is an efficient sorting algorithm with a time complexity of O(n log n). Its in-place sorting feature makes it memory efficient, while the use of a binary heap data structure allows it to perform well across various datasets.