Heap Sort Using Python

Heap sort is a comparison-based sorting algorithm that works by building a max heap (or min heap) from the input list and extracting the maximum (or minimum) element from the heap repeatedly until the heap is empty.

def heap_sort(arr):
    # Convert the input list into a max heap
    n = len(arr)
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    
    # Extract the elements from the heap one by one
    for i in range(n-1, 0, -1):
        # Swap the root element (maximum value) with the last element
        arr[i], arr[0] = arr[0], arr[i]
        # Re-heapify the remaining elements
        heapify(arr, i, 0)

def heapify(arr, n, i):
    # Find the largest element among the root, left child, and right child
    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 the largest element is not the root, swap it with the root and heapify the affected sub-tree
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Test the function
arr = [5, 2, 4, 6, 1, 3]
heap_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6]

To build the heap, the function first converts the input list into a max heap by repeatedly "heapifying" the list, which means rearranging the elements of the list to satisfy the heap property (i.e., the value of each node is at least as large as the values of its children).

Once the heap is built, the function extracts the maximum element (i.e., the root of the heap) and swaps it with the last element of the heap. The heap size is reduced by one, and the remaining elements are heapified again to maintain the heap property. This process is repeated until the heap is empty and the list is sorted.

Heap sort has a time complexity of O(nlogn) in the average and worst case, which makes it more efficient than some other sorting algorithms, such as bubble sort and insertion sort. However, it is not an in-place sorting algorithm, because it requires additional space to store the heap.

Using Recursion

def heap_sort_recursive(arr, n):
    # Base case: the heap has only one element
    if n == 1:
        return
    
    # Swap the root element (maximum value) with the last element
    arr[0], arr[n-1] = arr[n-1], arr[0]
    
    # Re-heapify the remaining elements
    heapify_recursive(arr, 0, n-1)
    
    # Sort the remaining elements
    heap_sort_recursive(arr, n-1)

def heapify_recursive(arr, i, n):
    # Find the largest element among the root, left child, and right child
    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 the largest element is not the root, swap it with the root and heapify the affected sub-tree
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify_recursive(arr, largest, n)

# Test the function
arr = [5, 2, 4, 6, 1, 3]
heap_sort_recursive(arr, len(arr))
print(arr)  # Output: [1, 2, 3, 4, 5, 6]

This recursive implementation of heap sort works by repeatedly extracting the root element (maximum value) from the heap and re-heapifying the remaining elements. The function first swaps the root element with the last element of the heap and then heapifies the remaining elements. It then calls itself recursively to sort the remaining elements, until the heap has only one element left.

The time complexity of this recursive implementation of heap sort is still O(nlogn) in the average and worst case, because the function makes O(logn) recursive calls and each call takes O(n) time to heapify the remaining elements. However, the recursive implementation may be more difficult to understand and may not be as efficient as the iterative implementation.