Heap Sort Implementation in Python

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. Heap Sort works by building a max heap from the input array and repeatedly extracting the maximum element from the heap and placing it at the end of the sorted array. Heap Sort is an efficient algorithm for sorting large datasets, with a time complexity of O(n log n). In this article, we will discuss how to implement Heap Sort in Python, how the algorithm works, its time and space complexities, and provide examples with detailed explanations.

How Heap Sort Works

The Heap Sort algorithm works by first creating a binary heap from the input array. The binary heap is a complete binary tree in which each node is greater than or equal to its children if it’s a max heap, or less than or equal to its children if it’s a min heap. In Heap Sort, we use a max heap to sort the input array.

The steps involved in implementing Heap Sort can be summarized as follows:

1. Build a max heap from the input array
2. Repeatedly extract the maximum element from the heap and place it at the end of the sorted array
3. Repeat step 2 until all elements have been extracted from the heap

Heap Sort Implementation

Here is the implementation of Heap Sort in Python:

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

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

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

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

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

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

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

In this implementation, we define two functions: heapify and heap_sort. The heapify function takes an array, the size of the heap n, and an index i as input. The function compares the value of the node at index i with its left and right children and swaps the node with the child having the larger value if necessary. The heapify function is used to build the heap from the input array.

The heap_sort function takes an array as input and first builds a max heap from the input array using the heapify function. It then repeatedly extracts the maximum element from the heap and places it at the end of the sorted array. This process continues until all elements have been extracted from the heap, and the sorted array is returned.

Time and Space Complexity

The time complexity of Heap Sort is O(n log n), where n is the number of elements in the input array. This is because building the heap takes O(n) time, and each extraction from the heap takes O(log n) time, and we do this n times.

The space complexity of Heap Sort is O(1) because we are sorting the input array in place, and only a constant amount of additional space is required for the heapify operation.

Example

Let’s see an example of how Heap Sort works:

arr = [7, 2, 4, 1, 5, 3]
heap_sort(arr)
print(arr)

Output:

[1, 2, 3, 4, 5, 7]

In this example, we have an input array of [7, 2, 4, 1, 5, 3]. After building the max heap, we extract the maximum element (7) and place it at the end of the sorted array. We repeat this process until all elements have been extracted from the heap, resulting in a sorted array of [1, 2, 3, 4, 5, 7].

Conclusion

Heap Sort is a highly efficient sorting algorithm for large datasets, with a time complexity of O(n log n). It works by building a binary heap from the input array and repeatedly extracting the maximum element from the heap to place it in the sorted array. In this article, we discussed the implementation of Heap Sort in Python, how the algorithm works, and its time and space complexities. We also provided an example with a detailed explanation of the output. With this knowledge, you should now be able to implement Heap Sort in Python for your own projects.