Heap Sort Algorithm

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is an in-place algorithm, meaning it requires only a constant amount of additional memory space. The algorithm works by building a max heap (or min heap) from the input data, then repeatedly extracting the maximum (or minimum) element from the heap and rebuilding the heap until all elements are sorted.

Heap Sort is efficient with a time complexity of O(n log n) for both the average and worst cases. However, it is not a stable sort, meaning it does not preserve the relative order of equal elements.

Heap Sort Algorithm Implementation in Python

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[left] > arr[largest]:
            largest = left

        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    n = len(arr)

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

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

    return arr

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

Code Explanation

Function Definition

def heap_sort(arr):

• The heap_sort function is defined to take a single list arr as its parameter.

Heapify Function

    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[left] > arr[largest]:
            largest = left

        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

• The heapify function ensures the subtree rooted at index i satisfies the heap property.
• largest is initialized to i.
• left and right are the indices of the left and right children of the node at index i.
• The function checks if the left and right children are larger than the root (i).
• If so, largest is updated to the index of the larger child.
• If largest is not i, the root is swapped with the larger child, and heapify is called recursively on the affected subtree.

Build the Max Heap

    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

• The variable n holds the length of the array.
• The for loop builds a max heap by calling heapify on each non-leaf node, starting from the last non-leaf node to the root node.

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)

• The for loop extracts elements from the heap one by one by swapping the root (maximum element) with the last element in the heap and reducing the heap size by 1.
• The heapify function is called on the reduced heap to restore the heap property.

Return Statement

    return arr

• The sorted array arr is returned.

Example Usage

arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("Sorted array is:", sorted_arr)

• An example list arr is sorted using the heap_sort function, and the sorted list is printed.

Output

Sorted array is: [5, 6, 7, 11, 12, 13]

• The final output is the sorted array in ascending order.

Summary

Heap Sort is an efficient, in-place sorting algorithm that uses a binary heap data structure to sort elements. It builds a max heap from the input data, then repeatedly extracts the maximum element from the heap and rebuilds the heap until all elements are sorted. The algorithm has a time complexity of O(n log n) for both average and worst cases, making it suitable for large datasets. However, it is not a stable sort, meaning it does not preserve the relative order of equal elements.